CYK ALGORITHM

CONTEXT FREE GRAMMARS

PRINCIPLE OF PROGRAMMING LANGUAGES

CYK ALGORITHM

CYK ALGORITHM

Consider the following grammar:

$A$::$=BH|C$ I $|FJ|c$

$H$::$=DB$

$B$::$=C$ I $|FJ|c$

$|$::$=EC$

$C$::$=FJ|c$

$J$::$=AG$

$A$::$=a$

$B$::$=b$

::$=c$

$D$::$=d$

$E$::$=e$

$F$::$=f$

$G$::$=g$

Spaces are used to separate symbols.

Which of the following strings can it generate?

f d e $g$

f c d c g e c

g c d c f e c

$cdc$