CYK algorithm: Difference between revisions

Revision as of 17:20, 30 January 2009

Revision as of 03:45, 2 February 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 written thuslythus. <ref>{{Citation

| last=Sipser

| first=Michael