Cocke-Younger-Kasami (CYK) Proving a word is in a language

178 Views Asked by At

Using CYK algorithm I need to figure out whether the word abbabb is a word of the language of the following grammar.

I think I have completed the problem correctly but I'm not sure, I'm hoping someone can confirm if my answer is correct or show me where I have gone wrong.

Question - Prove that the word abbabb is a word of the following grammar.

S --> XA|YB|SS|BB

X --> AS

Y --> BS

A --> a

B --> b

Finished table

1

There are 1 best solutions below

1
On

I do not know the CYK algorithm but I can establish that it is a word by elementary means:

$a\ bb\ a\ bb$

$\in a\ BB\ a\ BB$

$\subset a\ S\ a S$

$\subset AS\ A\ S$

$\subset XA\ S$

$\subset SS$

$\subset S.$