CYK algorithm: Difference between revisions

Revision as of 22:13, 20 July 2010

Revision as of 22:18, 20 July 2010

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 transformed to a CNF grammar expressing the same language.<ref> {{Citationharv|Sipser|1997}}.

| 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>

In the [[theory of computation]], the importance of the CYK algorithm stems from the fact that it constructively proves that it is [[decision problem|decidable]] whether a given [[string (computer science)|string]] belongs to the [[formal language]] described by a given [[context-free grammar]], and the fact that it does so quite efficiently.

Line 68 ⟶ 59:

===Parsing non-CNF context-free grammars===

As pointed out by {{harvtxt|Lange and |Leiß (|2009)}}, the drawback of all known transformations into Chomsky normal form is that they can lead to an undesirable bloat in grammar size. Using ''g'' to denote the size of the original grammar, the size blow-up in the worst case may range from <math>g^2</math> to <math>2^{2 g}</math>, depending on the used transformation algorithm. For the use in teaching, they propose a slight generalization of the CYK algorithm, "without compromising efficiency of the algorithm, clarity of its presentation, or simplicity of proofs" ({{harv|Lange and |Leiß |2009)}}.

===Parsing weighted context-free grammars===

Line 91 ⟶ 82:

* [[Donald E. Knuth]]. ''The Art of Computer Programming Volume 2: Seminumerical Algorithms''. Addison-Wesley Professional; 3 edition (November 14, 1997). ISBN 978-0201896848. pp. 501.

* Martin Lange and Hans Leiß. [http://www.informatica-didactica.de/InformaticaDidactica/LangeLeiss2009 ''To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm''.] Informatica Didactica 8, 2009. [http://www.informatica-didactica.de/InformaticaDidactica/LangeLeiss2009.pdf (pdf)]

*{{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

}}

*{{Cite journal

| last = Lee