The CYK Algorithm Visualization Tool

Word:

Grammar:
S -> AB A -> CD | CF B -> c | EB C -> a D -> b E -> c F -> AD

Step:

The Cocke–Younger–Kasami-Algorithm (CYK or CKY) is a highly efficient parsing algorithm for context-free grammars. This makes it ideal to decide the word-problem for context-free grammars, given in Chomsky normal form (CNF). The following tool can be used to check if a certain word \(w\in\Sigma^*\) is part of a language, given in CNF grammar.

Informally, the algorithm works as follows: In the first step write the word in the first row and add each non-terminal symbol in the row underneath which deduces the terminal symbols. After that, for each cell in the grid start vertically at the top and go down towards the cell to be checked and the second cell up in diagonal. For each such step, combine the cells and check if the combination appears in the grammar. If it does, add the left-hand-side non-terminal to the grid-cell. If after all steps the start-symbol is contained in the last row, the word can be derived by the given grammar.

The CYK algorithm calculator is written in JavaScript that can be read in the source of this page.

Cite the CYK Algorithm Tool

@misc{Eisele_2018, 
   title={A CYK Algorithm Visualization}, 
   url={https://raw.org/tool/cyk-algorithm/}, 
   author={Eisele, Robert}, 
   year={2018}, 
   month={May}
}