CYK algorithm: Difference between revisions

Revision as of 15:39, 14 July 2020

Revision as of 02:55, 25 September 2020

Line 1:

In [[computer science]], the '''Cocke–Younger–Kasami algorithm''' (alternatively called '''CYK''', or '''CKY''') is a [[parsing]] [[algorithm]] for [[context-free grammar]]s, invented by Itiroo Sakai.<ref>{{cite book |last1=Grune |first1=Dick |title=Parsing techniques : a practical guide |date=2008 |publisher=Springer |___location=New York |isbn=978-0-387-20248-8 |edition=2nd}}</ref> The algorithm is named after some of its inventors,rediscoverers: [[John Cocke]], Daniel Younger and [[Tadao Kasami]]. It employs [[bottom-up parsing]] and [[dynamic programming]].

The standard version of CYK operates only on context-free grammars given in [[Chomsky normal form]] (CNF). However any context-free grammar may be transformed (after convention) to a CNF grammar expressing the same language {{harv|Sipser|1997}}.