CYK algorithm: Difference between revisions

Revision as of 04:17, 5 July 2022

Revision as of 07:40, 5 July 2022

Line 16:

==Standard form==

The [[dynamic programming]] algorithm requires the context-free grammar to be rendered into [[Chomsky normal form]] (CNF), because it tests for possibilities to split the current sequence into two smaller sequences. Any context-free grammar that does not generate the empty string can be represented in CNF using only [[Formal grammar#The syntax of grammars|production rules]] of the forms <math>A\rightarrow \alpha</math>, <math>A\rightarrow B C</math>, and <math>S\to \varepsilon</math> where <math>S</math> is the start symbol.<ref>{{Cite book |last=Sipser |first=Michael |url=https://www.worldcat.org/oclc/58544333 |title=Introduction to the theory of computation |date=2006 |publisher=Thomson Course Technology |isbn=0-534-95097-3 |edition=2nd ed |___location=Boston |at=Definition 2.8 |oclc=58544333}}</ref>

==Algorithm==