Content deleted Content added
→As pseudocode: marked up comments as italic |
<references /> Sipser |
||
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 thusly. <ref>{{Citation
| last=Sipser
| first=Michael
| title=Introduction to the Theory of Computation
| publisher=IPS
| year=1997
| edition=1st
| page=99
| isbn =0-534-94728-X
}}</ref>
The importance of the CYK algorithm stems from the fact that it constructively proves that the [[membership problem]] for context-free languages is [[decision problem|decidable]] (see also: [[theory of computation]]) and the fact that it does so quite efficiently.
Line 64 ⟶ 73:
==References==
<references />
* [[John Cocke]] and Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University.
* [[Tadao Kasami|T. Kasami]] (1965). An efficient recognition and syntax-analysis algorithm for context-free languages. Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA.
| |||