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).

Short Howto
The tabs are being processed from left to right doing the following.
  1. 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 ;

  2. The grammar is transformed into 2NF, a normal form much weaker than Chomsky Normal Form.
  3. The nullable symbols of the grammar are being computed. This step is also present in the usual transformation into CNF.
  4. The inverse chain relation is being displayed. For every symbol x (nonterminal or terminal) you can see those nonterminals A that can derived x.
  5. The CYK table is being filled on a given input string (consisting of nonterminals or terminals).
Known Bugs