CYK algorithm: Difference between revisions

Revision as of 21:14, 27 November 2023

Latest revision as of 03:56, 17 July 2025

(7 intermediate revisions by 7 users not shown)

Line 1:

{{Short description|Parsing algorithm for context-free grammars}}

{{Redirect|CYK||Cyk (disambiguation)}}

{{Infobox algorithm

|name=Cocke–Younger–Kasami algorithm (CYK)

Line 16 ⟶ 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==

Line 40 ⟶ 42:

append <p,b,c> to ''back''[''l'',''s'',''a'']

'''if''' ''P''[n,''1'','' s1''] is true '''then'''

''I'' is member of language

'''return''' ''back'' -- by ''retracing the steps through back, one can easily construct all possible parse trees of the string.''

Line 168 ⟶ 170:

==External links==

* [https://raw.org/tool/cyk-algorithm/ Interactive Visualization of the CYK algorithm]

* [https://martinlaz.github.io/demos/cky.html CYK parsing demo in JavaScript]

* [https://www.swisseduc.ch/informatik/exorciser/ Exorciser is a Java application to generate exercises in the CYK algorithm as well as Finite State Machines, Markov algorithms etc]