Content deleted Content added
→Standard form: clarification on the empty string Tags: Mobile edit Mobile app edit Android app edit |
Citation bot (talk | contribs) Removed URL that duplicated identifier. | Use this bot. Report bugs. | #UCB_CommandLine |
||
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, one can explicitly allow <math>S\to \varepsilon</math>, where <math>S</math> is the start symbol.<ref>{{Cite book |last=Sipser |first=Michael
==Algorithm==
| |||