SeeYK - A Visualisation of the CYK Algorithm
The following applet visualises how the CYK algorithm solving the word problem for
context-free grammars works. Note that the procedure implemented here differs slightly
from many textbook presentations. In particular, it avoids the transformation of the
grammar into Chomsky Normal Form. The entire procedure is described in detail in
M. Lange, H. Leiß, To CNF or not to CNF? An Efficient Yet Presentable Version of the
CYK Algorithm, accepted for publication in Informatica Didactica, 2009
(preliminary version available as PDF)
The implementation is prototypical, please report bugs to the author
(martin dot lange at ifi dot lmu dot de).
The tabs are being processed from left to right doing the following.
- Enter a grammar. Nonterminals start with capital letters, terminal symbols with non-capital
ones. The disjunction is a vertical bar, rule definitions are introduced by a colon and
ended by a semicolon. The empty word is the empty string. Whitespaces are separators. Example:
A : a B | c B | ; B : b b b ;
- The grammar is transformed into 2NF, a normal form much weaker than Chomsky Normal Form.
- The nullable symbols of the grammar are being computed. This step is also present in the
usual transformation into CNF.
- The inverse chain relation is being displayed. For every symbol x (nonterminal or
terminal) you can see those nonterminals A that can derived x.
- The CYK table is being filled on a given input string (consisting of nonterminals or
- Highlighting in the "Show inverse chain relation" tab can go ballistic.
- Transformation into 2NF is also possible on incorrect input.