The CYK algorithm is a bottom-up dynamic programming algorithm for Context free grammars in Chomsky normal form, to see if an input string can be generated by a given grammar.

Recall Chomsky Normal Form.

Given an input string, we want to create the following table:

where $M[i,j]$ denotes the substring of length $i$ starting at $y_j$.

All lengths $i$ are on the side, and all characters of the input string $y_j$ are on the bottom.

<aside> 🆕 We can then look at the top left cell - if that contains $S$, we know our grammar can generate the string.

</aside>

An example

Consider the input string

$aaabbb$

and the grammar with rules

$S \rightarrow \epsilon|AB|XB$

$T \rightarrow AB|XB$

$X \rightarrow AT$

$A \rightarrow a$

$B \rightarrow b$

Step by step

This table actually gives us the parse tree as well: