CYK algorithm: Difference between revisions

Revision as of 14:28, 15 March 2024

Latest revision as of 03:56, 17 July 2025

(One intermediate revision by one other user not shown)

Line 18:

==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>; to allow for the empty string, andone can explicitly allow <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 |___location=Boston |at=Definition 2.8 |oclc=58544333}}</ref>

==Algorithm==