CYK

The Cocke-Younger-Kasami (CYK) algorithm is a bottom-up parser for context-free grammars in Chomsky normal form. It determines whether a given string can be generated by a grammar and can construct a corresponding parse tree if one exists. The algorithm is widely taught in formal language theory and is used in some natural language processing and compiler tasks.

Background and prerequisites: The CYK algorithm was developed independently by John Cocke, Tadao Younger, and Tsuyoshi Kasami in the 1960s. It requires the grammar to be in Chomsky normal form, where every production is either A → BC or A → a (a terminal). If a grammar is not already in CNF, it can be transformed into an equivalent CNF grammar, though the transformation may increase the size of the grammar.

Algorithm description: The CYK algorithm uses a dynamic programming table T of size n by n for an input string of length n. Each cell T[i, j] holds the set of nonterminals that derive the substring of length j starting at position i. The base case fills the diagonal with nonterminals that derive each terminal symbol. For longer substrings, the algorithm considers all partitions of the substring and uses productions A → BC to combine the results from two smaller substrings, adding A to the cell if B and C are derivable for the respective parts. A parse exists if the start symbol is present in the top-right cell, and backpointers can reconstruct a parse tree.

Complexity and notes: Time complexity is O(n^3 · |P|) in general, often treated as O(n^3) for a fixed grammar. Space complexity is O(n^2). While it guarantees a parse for CNF grammars, CYK can be less practical for large grammars or strings and is typically used for theoretical analysis, education, or specific parsing tasks where CNF is appropriate.