CYK algorithm: Difference between revisions

Revision as of 22:21, 28 May 2022

Revision as of 03:21, 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> and, <math>A\rightarrow B C</math>., and <math>S\to \varepsilon</math> where <math>S</math> is the start symbol.<ref>{{CitationCite book |last=Sipser |first=Michael |url=https://www.worldcat.org/oclc/58544333 |title=Introduction to the theory of computation needed|date=September2006 2021|publisher=Thomson Course Technology |isbn=0-534-95097-3 |edition=2nd ed |___location=Boston |at=Definition 2.8 |oclc=58544333}}</ref>

==Algorithm==