Is CYK also called CKY?

Yes. Both orderings of the initials are widely used for this parsing family.

Must the original grammar already be in Chomsky normal form?

It can be transformed for the standard algorithm. That transformation and any empty-string handling must preserve the intended language.

Can probabilities be added?

Yes. Probabilistic variants combine rule scores and chart values, but choosing the most probable parse and summing over parses require different aggregation operations.

AI Glossary / Graphs and symbolic AI / Advanced

CYK algorithm

Definition

The CYK algorithm, named for Cocke, Younger and Kasami, is a dynamic programming method for recognizing and parsing strings with a context-free grammar. Its standard form uses Chomsky normal form and builds answers for larger substrings from answers already found for smaller ones.

What it means

A grammar describes how symbols can combine into valid structures. A parser asks whether an input follows those rules and, when required, how its parts fit together. CYK organizes this work in a chart instead of repeatedly solving the same substring problem.

Each chart cell corresponds to a contiguous span of input. It records the grammar symbols that can generate that span. A completed chart can show whether the grammar's start symbol generates the whole input.

Recognition and parsing are related but distinct. A Boolean chart can answer yes or no. Recovering a parse tree requires remembering the rule and split that justified an entry. Keeping several alternatives permits ambiguous structures to be represented without immediately choosing one.

How it works

In the standard nonempty-input formulation, grammar rules have forms A→BC or A→a: a nonterminal expands into two nonterminals or into one terminal. Handling the empty string needs the relevant start-symbol convention and a separate check.

Initialize length-one spans using terminal rules. If the token at a position is a and the grammar contains A→a, record A for that position. Then process spans of length two, three and so on.

For each span, try each possible split into two nonempty adjacent spans. If B generates the left span, C generates the right, and a rule A→BC exists, record A for the combined span. The table reuses earlier results because both child spans are shorter.

Accept when the start symbol appears in the cell covering the complete input. For a fixed grammar, the usual chart computation takes cubic time in input length and quadratic chart space. Grammar size affects the fuller bound, and storing or explicitly listing all parse trees can cost much more than a simple recognition chart.

Three practical examples

A language-processing lesson uses a small grammar to show how sentence constituents combine without recomputing every candidate phrase.
A validator checks whether a short structured command belongs to a specified context-free language.
A grammar researcher uses chart backpointers to inspect multiple parses and locate an ambiguous rule combination.

Think of it this way

Think of assembling a wall from smaller blocks while recording which shapes can cover each interval. Once a small interval is understood, its result can be reused when constructing a larger interval.

Unlike a physical wall, one chart interval can have several valid grammatical labels or structures simultaneously. The algorithm preserves alternatives instead of assuming that the first successful arrangement is the only one.

Worked example

Building a three-token chart

Use the grammar S→AB, A→a, B→CD, C→b and D→c. Its start symbol is S. The input is the three-token string a b c.

For length-one spans, the first token receives A, the second C and the third D. For the two-token span a b, there is no rule whose right side is A C, so no new nonterminal is recorded. For b c, rule B→CD records B.

For the full span a b c, split after the first token. The left span has A and the right has B, so S→AB records S. Splitting after the second token contributes nothing because a b has no matching nonterminal. Since S covers the entire input, it is accepted.

A backpointer for S identifies the split and rule; the pointer for B identifies its two children. Together they reconstruct S(A(a), B(C(b), D(c))). The input a c b would fail because the required ordered combination C D is absent. Matching the same collection of tokens is not enough.

Illustrative case study

A fictional workflow-tools team, Cedar Syntax, defines a small language for internal commands. It uses a chart parser during grammar experiments so that developers can inspect why an input is accepted.

One test command receives two distinct parse structures. The team initially treats that as a parser error, but inspection shows that both follow the grammar's rules. The ambiguity belongs to the grammar, not to a failure of dynamic programming.

The developers decide whether the language should forbid that ambiguity or attach a separate interpretation rule. They also preserve mappings from transformed grammar rules to their original forms, so that parse explanations remain understandable after conversion to Chomsky normal form.

Common misconceptions and mistakes

CYK learns a grammar from examples. The standard algorithm receives a grammar; learning its rules is a separate task.
Successful parsing proves a sentence is meaningful or true. It establishes grammatical membership under the supplied rules.
Cubic chart construction means listing all parse trees is cubic. An ambiguous grammar can have many possible trees.
Every input token must correspond to exactly one grammar category. A chart can record several categories where the grammar permits them.

Business use

CYK is useful for understanding structured language processing and for applications that need general context-free parsing with explicit intermediate results. Its chart provides a transparent record of which spans can be explained by which rules.

For a production language tool, assess grammar size, expected input length, ambiguity and the output required. A membership decision, one preferred parse and every possible parse are different workloads. Grammar conversion may introduce auxiliary symbols, so preserve the connection between technical chart entries and the structures users need to understand.

Check your understanding

A chart contains the start symbol for a middle substring but not for the complete input. Has CYK accepted the whole input?

Answer: No. Acceptance requires the start symbol to generate the complete input span, not merely one of its parts.

Related terms

Learn next

Construct the chart for the example grammar by hand, then add a second rule path producing the same input. Record both backpointer alternatives. Separate the questions “is it accepted?”, “what is one parse?” and “how many parses exist?”.

Sources

Lawrence Larmore, University of Nevada, Las Vegas, The CYK Algorithm, explains the substring table and bottom-up recognition procedure: https://web.cs.unlv.edu/larmore/Courses/CSC456/cyk.html

Alfred Aho, Columbia University, lecture material on context-free grammars and Chomsky normal form: https://www.cs.columbia.edu/~aho/cs3261/Lectures/L9-CFGs_and_PDAs.html

The grammar, chart walkthrough and Cedar Syntax case are original teaching examples.

Previous: Cyclodisparity Next: D*