The Cocke-Younger-Kasami algorithm, usually abbreviated as CYK or CKY, decides whether a word belongs to a context-free language. It does more than return yes or no: the triangular chart records which nonterminal can derive every contiguous span of the input. That structure makes the algorithm useful for teaching formal languages, inspecting ambiguous grammars, and building small parsers.
The visualizer above accepts grammars in Chomsky normal form (CNF), animates every terminal lookup and split, and exposes the productions behind each chart cell. Compact one-character notation and descriptive nonterminal names are both supported. The dynamic-programming recurrence behind the chart, the complexity analysis, and the historical background are derived separately in an introduction to the CYK algorithm.
Grammar Requirements
CYK requires each production to have one of two forms:
\[ A \to BC \qquad\text{or}\qquad A \to a, \]where \(A,B,C\) are nonterminals and \(a\) is a terminal. Rules such as \(A\to B\), alternatives containing three nonterminals, and mixed terminal/nonterminal right-hand sides are not in CNF and must be converted first. Strict CNF cannot derive the empty word, so the visualizer requires at least one input token; if \(\varepsilon\) belongs to the original language, that fact needs to be tracked separately.
For single-character words, write terminal rules directly, for example C -> a. For a token stream such as id + id, separate the input tokens with spaces and quote multi-character terminals in the grammar:
Expr -> Left Tail
Left -> "id"
Tail -> Plus Right
Plus -> "+"
Right -> "id" Reading the Visualization
The input tokens form the bottom edge. Cells immediately above them contain the nonterminals that produce one terminal. Higher cells represent increasingly long substrings until the top cell spans the complete input. During playback, the dark cell is the destination currently being updated; outlined cells are the two subspans combined at that split.
Clicking a cell reveals every recorded derivation. Several derivations for the same symbol indicate local ambiguity: the substring can be generated in more than one way. The chart therefore contains enough information to reconstruct parse trees by following the stored split positions recursively.
Worked Example
The default grammar recognizes words assembled from blocks generated by \(A\), followed by one or more c terminals generated by \(B\). For aaabbbcc, terminal rules first place \(C\), \(D\), \(B\), and \(E\) in the length-one cells. Binary rules then build larger constituents. The final cell contains \(S\), so the word is accepted.
Changing the input to a word that cannot be covered by compatible adjacent constituents leaves \(S\) out of the top cell. This is a structural rejection, not a search timeout: every possible split has been checked.
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}
}