CYK algorithm

Summary

The Cocke–Younger–Kasami (CYK) algorithm decides whether a word belongs to the language of a context-free grammar in Chomsky normal form. It is a dynamic programming method that finds, for each substring of the word, the set of nonterminals that derive it. It runs in time cubic in the length of the word, so the membership problem for context-free languages is solvable in polynomial time. It also yields parse trees, so it serves as a general parsing algorithm.