Content deleted Content added
moved description of non-CNF extension to section ===Algorithm extensions=== |
→The algorithm: Rephrasing |
||
Line 7:
==The algorithm==
The CYK algorithm is
The algorithm employs [[bottom-up parsing]].
▲The CYK algorithm is a [[bottom-up parsing|bottom up]] algorithm and is important theoretically, since it can be used to constructively prove that the [[membership problem]] for context-free languages is [[decision problem|decidable]].
▲The CYK algorithm for the membership problem is as follows:
'''Let''' the input string consist of ''n'' letters, ''a''<sub>1</sub> ... ''a''<sub>''n''</sub>.
'''Let''' the grammar contain ''r'' terminal and nonterminal symbols ''R''<sub>1</sub> ... ''R''<sub>''r''</sub>.
| |||