CYK algorithm
Parsing algorithm for contextfree grammars / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about CYK algorithm?
Summarize this article for a 10 year old
In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for contextfree grammars published by Itiroo Sakai in 1961.^{[1]}^{[2]} The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. It employs bottomup parsing and dynamic programming.
Class  Parsing with contextfree grammars 

Data structure  String 
Worstcase performance  ${\mathcal {O}}\left(n^{3}\cdot \leftG\right\right)$, where:

The standard version of CYK operates only on contextfree grammars given in Chomsky normal form (CNF). However any contextfree grammar may be algorithmically transformed into a CNF grammar expressing the same language (Sipser 1997).
The importance of the CYK algorithm stems from its high efficiency in certain situations. Using big O notation, the worst case running time of CYK is ${\mathcal {O}}\left(n^{3}\cdot \leftG\right\right)$, where $n$ is the length of the parsed string and $\leftG\right$ is the size of the CNF grammar $G$ (Hopcroft & Ullman 1979, p. 140). This makes it one of the most efficient ^{[citation needed]} parsing algorithms in terms of worstcase asymptotic complexity, although other algorithms exist with better average running time in many practical scenarios.