CYK algorithm: Difference between revisions

Revision as of 07:54, 22 October 2009

Revision as of 22:22, 1 December 2009

Line 2:

[[string (computer science)|string]] can be generated by a given [[context-free grammar]] and, if so, how it can be generated. This is known as [[parsing]] the string. The algorithm employs [[bottom-up parsing]] and [[dynamic programming]].

The standard version of CYK operates on context-free grammars given in [[Chomsky normal form]] (CNF). Any context-free grammar may be writtentransformed thusto a CNF grammar expressing the same language.<ref>{{Citation

| last=Sipser

| first=Michael