47.01.06 · theoretical-cs / formal-languages-automata

Pumping Lemma for Context-Free Languages and CYK Parsing

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §2.3-2.4; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §7.4 (CYK with Chomsky normal form conversion, Ogden's lemma as a strengthening)

Intuition Beginner

Think of a family tree. Each person has two parents. If you go back enough generations, with enough people in each generation, you will eventually find that two people on the same ancestral path share the same last name. That repeated name creates a loop in the tree.

A parse tree for a context-free grammar works the same way. The grammar has rules like "a sentence is a noun phrase plus a verb phrase." Each rule expands one symbol into two or more children. For a sufficiently long sentence, the tree must be tall. And since there are only finitely many grammar symbols, some symbol must appear twice on the same path from root to leaf.

That repeated symbol is the key. The subtree between the two appearances can be copied or deleted. Because the grammar is recursive (the same symbol produces itself), you can repeat the middle part as many times as you want, or remove it entirely, and the result is still a valid sentence in the language.

This is the context-free pumping lemma. Unlike the regular version (which has one pumpable region), the context-free version has two. The two regions come from the two subtrees of the repeated nonterminal. And unlike the regular version, the pumpable regions are bounded in total length: they must fit within a window of $p$ symbols.

The CYK algorithm solves the other direction: given a string, is it in the language? It works bottom-up, building a table of which substrings each nonterminal can produce. For every pair of adjacent substrings that $A$ can produce from $B$ and $C$ (where $A \to B C$ is a rule), mark $A$ as producing the combined span. After filling the table, the start symbol produces the whole string if and only if the string is in the language.

Visual Beginner

A parse tree with a repeated nonterminal on a path:

         S
        / \
       A    ...
      / \
     A    y        ← A repeats on the same path
    / \
   u    v          ← v and y are the two pumpable parts
        |
        x

Pumping both $v$ and $y$ simultaneously:

Version	String	In language?
$u v^{0} x y^{0} z = ux z$	Remove both $v$ and $y$	Yes (by pumping lemma)
$u v^{1} x y^{1} z = uv x y z$	Original string	Yes
$u v^{2} x y^{2} z = uv v x y y z$	Repeat both $v$ and $y$ once	Yes
$u v^{3} x y^{3} z = uv v v x y y y z$	Repeat both three times	Yes

The CYK table for deciding membership:

Input:  b  a  a  b  a

Span 1: [b] [a] [a] [b] [a]
Span 2: [ba] [aa] [ab] [ba]
Span 3: [baa] [aab] [aba]
Span 4: [baab] [aaba]
Span 5: [baaba]  ← Does S appear here?

Each cell stores the set of nonterminals that generate that substring.

Worked example Beginner

We prove that $L = {a^{n} b^{n} c^{n} : n \geq 0}$ is not context-free.

Suppose $L$ is context-free with pumping length $p$ . Choose $s = a^{p} b^{p} c^{p}$ . By the pumping lemma, $s = uv x y z$ where $∣ v y ∣ > 0$ , $∣ v x y ∣ \leq p$ , and $u v^{i} x y^{i} z \in L$ for all $i \geq 0$ .

Since $∣ v x y ∣ \leq p$ , the window $v x y$ cannot span all three letter types ( $a$ , $b$ , and $c$ ) at once. So $v$ and $y$ together contain at most two types of letters.

Case 1: $v x y$ lies entirely in the $a$ s and $b$ s. Pumping up ( $i = 2$ ) adds more $a$ s and/or $b$ s without adding $c$ s. The pumped string has more $a$ s and/or $b$ s than $c$ s, so it is not in $L$ .

Case 2: $v x y$ lies entirely in the $b$ s and $c$ s. Pumping up adds more $b$ s and/or $c$ s without adding $a$ s. The pumped string has more $b$ s and/or $c$ s than $a$ s, so it is not in $L$ .

In every case, pumping produces a string outside $L$ . Contradiction. So ${a^{n} b^{n} c^{n}}$ is not context-free.

Check your understanding Beginner

Formal definition Intermediate+

Lemma (Pumping lemma for context-free languages). Let $L$ be a context-free language. Then there exists a constant $p \geq 1$ such that every string $s \in L$ with $∣ s ∣ \geq p$ can be written as $s = uv x y z$ where:

For each $i \geq 0$ , $u v^{i} x y^{i} z \in L$ .
$∣ v y ∣ > 0$ (at least one of $v, y$ is nonempty).
$∣ v x y ∣ \leq p$ (the two pumpable regions fit within a window of length $p$ ).

Proof. Let $G = (V, Σ, R, S)$ be a CFG in Chomsky normal form generating $L ∖ {ε}$ with $∣ V ∣ = k$ nonterminals. Set $p = 2^{k}$ . Let $s \in L$ with $∣ s ∣ \geq p = 2^{k}$ . Consider the parse tree for $s$ . In CNF, every internal node has either 2 children (a nonterminal production $A \to B C$ ) or 1 child (a terminal production $A \to a$ ). The yield of a subtree of height $h$ has length at most $2^{h - 1}$ (binary branching doubles at each level).

Since $∣ s ∣ \geq 2^{k}$ , the parse tree has height at least $k + 1$ . The longest path from root to leaf has at least $k + 1$ internal nodes. By pigeonhole, some nonterminal $A$ appears at least twice on this path. Consider the upper and lower occurrences of $A$ .

The upper $A$ generates a subtree whose yield contains $v x y$ . The lower $A$ generates a subtree whose yield contains $v$ and $y$ separated by $x$ . Since the path from the upper $A$ to the lower $A$ has at most $k + 1$ nodes, the yield of the subtree rooted at the upper $A$ has length at most $2^{k} = p$ , giving $∣ v x y ∣ \leq p$ . The yield of the lower $A$ subtree has $∣ v y ∣ > 0$ (otherwise $A \Rightarrow^{*} A$ , which is impossible in a proper CNF grammar without unit productions).

For any $i \geq 0$ , replacing the upper $A$ subtree by its $i$ -fold repetition (pump $i$ copies of the $A \to \dots A \dots$ derivation) produces a valid parse tree with yield $u v^{i} x y^{i} z$ . $□$

Algorithm (CYK). Given a CFG $G = (V, Σ, R, S)$ in Chomsky normal form and input string $w = a_{1} a_{2} \dots a_{n}$ :

For $1 \leq i \leq n$ : set $T [i, i] = {A \in V : A \to a_{i} \in R}$ .
For length $ℓ = 2, 3, \dots, n$ : for $1 \leq i \leq n - ℓ + 1$ : set $j = i + ℓ - 1$ , then $T [i, j] = {A : A \to B C \in R, \exists k with i \leq k < j, B \in T [i, k], C \in T [k + 1, j]}$ .
Accept iff $S \in T [1, n]$ .

The running time is $O (n^{3} \cdot ∣ R ∣)$ : there are $O (n^{2})$ table entries, and each entry examines $O (n)$ split points and $O (∣ R ∣)$ rules.

Counterexamples to common slips

"The CFL pumping lemma can prove a language is context-free." No. It is a necessary condition, not sufficient. There exist non-context-free languages that satisfy the pumping lemma conditions.
"Both $v$ and $y$ must be nonempty." Only their combined length $∣ v y ∣ > 0$ is required. One of them can be empty.
"The CYK algorithm produces a parse tree." The basic CYK algorithm only decides membership. It can be extended to recover a parse tree by storing back-pointers, but this is an additional step.

Key theorem with proof Intermediate+

Theorem. The following languages are not context-free:

(a) ${a^{n} b^{n} c^{n} : n \geq 0}$ . (b) ${w w : w \in {a, b}^{*}}$ . (c) ${a^{n^{2}} : n \geq 0}$ .

Proof of (a). Given pumping length $p$ , choose $s = a^{p} b^{p} c^{p}$ . Since $∣ v x y ∣ \leq p$ , the window cannot span all three letter types. If $v x y$ is within the $a$ s and $b$ s, pumping up increases $a$ s or $b$ s but not $c$ s; if within the $b$ s and $c$ s, pumping up increases $b$ s or $c$ s but not $a$ s. In both cases the pumped string has unequal counts. $□$

Proof of (b). Choose $s = a^{p} b^{p} a^{p} b^{p}$ . The window $∣ v x y ∣ \leq p$ fits within at most two of the four blocks. Pumping changes the counts within those blocks without matching the change in the corresponding position of the would-be repeated half. The resulting string is not of the form $w w$ . $□$

Proof of (c). Choose $s = a^{p^{2}}$ . Pumping up gives $a^{p^{2} + ∣ v ∣ + ∣ y ∣}$ . Since $1 \leq ∣ v y ∣ \leq p$ , we have $p^{2} < p^{2} + ∣ v y ∣ \leq p^{2} + p$ . For $p \geq 2$ : $(p + 1)^{2} = p^{2} + 2 p + 1 > p^{2} + p$ , so $p^{2} + ∣ v y ∣$ is not a perfect square. $□$

Bridge. The CFL pumping lemma builds toward the Chomsky hierarchy where each level (regular, context-free, context-sensitive, recursively enumerable) is separated by pumping arguments of increasing sophistication. This is exactly the structural pattern established by the regular pumping lemma in 47.01.04, now generalised from one pumpable region to two. The lemma appears again in 47.02.01 where the P-vs-NP question asks whether polynomial-time computation can solve all of NP, an analogous containment question to whether context-free grammars generate all of ${a^{n} b^{n} c^{n}}$ . The central insight is that parse-tree structure — specifically the branching factor of grammar rules — constrains the kinds of patterns a language can exhibit, and this is exactly what makes the CFL pumping lemma a strictly stronger tool than its regular counterpart. Putting these together with the CYK algorithm gives a complete picture: the pumping lemma provides negative evidence (what CFLs cannot do) while CYK provides positive evidence (efficient membership testing for what CFLs can do), and this duality between lower bounds and algorithms is the foundational reason theoretical computer science studies both simultaneously.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Run the CYK algorithm on the string "baab" with grammar $S \to A B ∣ B A ∣ S S$ , $A \to a ∣ A S$ , $B \to b ∣ B S$ (in CNF). Is "baab" in the language?

Hint

Fill the triangular table bottom-up. Start with single characters, then pairs, then triples, then the full string.

Answer

$T [1, 1] = {B}$ ( $B \to b$ ), $T [2, 2] = {A}$ ( $A \to a$ ), $T [3, 3] = {A}$ , $T [4, 4] = {B}$ .

$T [1, 2]$ : split at $k = 1$ : $T [1, 1] \times T [2, 2] = {B A}$ . $S \to B A$ gives $T [1, 2] = {S}$ .

$T [2, 3]$ : $T [2, 2] \times T [3, 3] = {AA}$ . No rule produces $AA$ . $T [2, 3] = \emptyset$ .

$T [3, 4]$ : $T [3, 3] \times T [4, 4] = {A B}$ . $S \to A B$ gives $T [3, 4] = {S}$ .

$T [1, 3]$ : splits $k = 1, 2$ . $k = 1$ : $T [1, 1] \times T [2, 3] = \emptyset$ . $k = 2$ : $T [1, 2] \times T [3, 3] = {S} \times {A} = {S A}$ . $A \to A S$ gives $T [1, 3] = {A}$ .

$T [2, 4]$ : splits $k = 2, 3$ . $k = 2$ : $T [2, 2] \times T [3, 4] = {A} \times {S} = {A S}$ . $A \to A S$ gives ${A}$ . $k = 3$ : $T [2, 3] \times T [4, 4] = \emptyset$ . $T [2, 4] = {A}$ .

$T [1, 4]$ : splits $k = 1, 2, 3$ . $k = 1$ : $T [1, 1] \times T [2, 4] = {B} \times {A} = {B A}$ . $S \to B A$ gives ${S}$ . $k = 2$ : $T [1, 2] \times T [3, 4] = {S} \times {S} = {S S}$ . $S \to S S$ gives ${S}$ . $k = 3$ : $T [1, 3] \times T [4, 4] = {A} \times {B} = {A B}$ . $S \to A B$ gives ${S}$ . $T [1, 4] = {S}$ .

Since $S \in T [1, 4]$ , "baab" is in the language.

Exercise 5 (medium, symbolic).

Prove that $L = {a^{i} b^{j} c^{k} : i < j < k}$ is not context-free.

Hint

Choose $s = a^{p} b^{p + 1} c^{p + 2}$ . The window $∣ v x y ∣ \leq p$ restricts which letters can appear together.

Answer

Choose $s = a^{p} b^{p + 1} c^{p + 2}$ with pumping length $p$ . The window $v x y$ with $∣ v x y ∣ \leq p$ spans at most two consecutive letter types. If $v x y$ is in $a$ s and $b$ s, pumping down reduces $a$ s or $b$ s. Pumping down $a$ s gives $a^{p - ∣ v_{y} ∣} b^{p + 1} c^{p + 2}$ where $∣ v_{y} ∣ > 0$ within the $a$ - $b$ region. If $v$ consists of $a$ s, then after pumping down, the $a$ -count decreases while $b$ and $c$ counts stay the same, potentially still satisfying $i < j < k$ . However, pumping up adds $a$ s or $b$ s: if pumping adds only $b$ s, then $b$ -count becomes $p + 1 + ∣ y ∣ \geq p + 2 = c$ -count, violating $j < k$ . If $v x y$ is in $b$ s and $c$ s, similar analysis with pumping shows the strict inequality fails. In every case, some pumped version escapes the language. Contradiction.

Exercise 6 (hard, symbolic).

Prove that $L = {a^{n} b^{n} a^{n} b^{n} : n \geq 0}$ is not context-free.

Hint

Choose $s = a^{p} b^{p} a^{p} b^{p}$ . The window $∣ v x y ∣ \leq p$ cannot span both "halves" of the string.

Answer

Choose $s = a^{p} b^{p} a^{p} b^{p}$ with pumping length $p$ . Since $∣ v x y ∣ \leq p$ , the window cannot simultaneously cover part of the first $a^{p} b^{p}$ and the second $a^{p} b^{p}$ (the gap between them is too large). So $v x y$ is contained within either the first half ( $a^{p} b^{p}$ ) or straddles the boundary between the first $b^{p}$ and the second $a^{p}$ or is in the second half.

If $v x y$ is in the first $a^{p} b^{p}$ : pumping changes the first half without changing the second half, so the two halves no longer match.

If $v x y$ straddles the $b$ -to- $a$ boundary in the middle: pumping changes the middle $b$ s and $a$ s, disrupting the equality of both the $b$ -counts and the second $a$ -count simultaneously.

If $v x y$ is in the second $a^{p} b^{p}$ : pumping changes the second half without matching the first. In all cases, pumping produces a string not in $L$ . Contradiction.

Exercise 7 (hard, symbolic).

Show that the CFL pumping lemma cannot prove that ${a^{n} b^{n} c^{n} : n \geq 0}$ is not context-free if we only use the regular pumping lemma style (one pumpable region).

Answer

Consider a hypothetical "single-region" pumping lemma for CFLs where $s = x y z$ and $x y^{i} z \in L$ . The language ${a^{n} b^{n} c^{n}}$ would not be disproved by such a lemma: any string $a^{p} b^{p} c^{p}$ can have $y$ within a single letter block, and pumping within a single block changes only one count while the other two stay equal, which might still fail the three-way equality. But the crucial point is that the CFL pumping lemma's two-region structure is necessary to capture the branching nature of parse trees. A single-region version would fail to exploit the grammar structure. The actual proof works because the two regions $v$ and $y$ are generated by the two branches of a repeated nonterminal, and the constraint $∣ v x y ∣ \leq p$ forces both regions to be "local" in the string while being "distant" in the parse tree.

Lean formalization Intermediate+

Mathlib has Computability.ContextFreeGrammar with basic grammar definitions but lacks CNF conversion, the CFL pumping lemma, and the CYK algorithm. The foundational gap is the absence of a verified CNF conversion procedure, a ContextFree.pumping_lemma theorem, and a ContextFree.cyk_membership decision procedure with a correctness proof. The CYK algorithm would be a natural target for formalisation because its dynamic-programming structure maps well to induction on span length. This unit ships without a lean_module.

Advanced results Master

Three results sharpen the CFL pumping lemma and its algorithmic consequences.

Theorem 1 (Ogden's lemma). Let $L$ be context-free. Then there exists $p$ such that for any string $s \in L$ with $∣ s ∣ \geq p$ and any marking of at least $p$ positions of $s$ as "distinguished," $s = uv x y z$ with (1) $v y$ contains at least one distinguished position, (2) $v x y$ contains at most $p$ distinguished positions, and (3) $u v^{i} x y^{i} z \in L$ for all $i \geq 0$ ^{[Hopcroft, Motwani & Ullman §7.4]}.

Ogden's lemma is strictly stronger than the CFL pumping lemma. It can prove languages non-context-free that the ordinary pumping lemma cannot handle. For example, $L = {a^{i} b^{j} c^{k} d^{l} : i = 0 or j = k = l}$ is not context-free, but the ordinary pumping lemma fails to prove it because the $i = 0$ case gives too many strings that pump without issue. Ogden's lemma resolves this by marking the $b$ , $c$ , and $d$ positions as distinguished.

Theorem 2 (CYK optimality). The CYK algorithm runs in $O (n^{3} ∣ G ∣)$ time and $Θ (n^{2})$ space. For general CFGs, this is optimal under the strong exponential time hypothesis (SETH), though faster algorithms exist for restricted grammar classes.

The Valiant algorithm (1975) reduces CYK-style parsing to Boolean matrix multiplication, achieving $O (n^{2.373})$ time using the current best matrix multiplication algorithms. However, the practical constant factors make CYK preferable for moderate-length inputs.

Theorem 3 (Parikh's theorem). Every context-free language over a unary alphabet is regular. More generally, the Parikh image of any CFL (the set of letter-count vectors) is a semilinear set ^{[Sipser §2.3]}.

Parikh's theorem implies that the CFL pumping lemma can never prove non-context-freeness of a unary language, because all unary CFLs are regular and hence satisfy the regular pumping lemma. The theorem connects the algebraic structure of CFLs to Presburger arithmetic.

Synthesis. The CFL pumping lemma is the foundational reason that context-free languages form a proper superset of regular languages while remaining strictly below context-sensitive languages: the central insight is that the binary branching of parse trees allows two simultaneous pumping regions, and this is exactly what enables CFLs to match paired structures like ${a^{n} b^{n}}$ while still failing on triple structures like ${a^{n} b^{n} c^{n}}$ . This builds toward the Chomsky hierarchy where each level is separated by increasingly sophisticated pumping arguments. The CYK algorithm provides the algorithmic dual: it exploits the same binary branching structure for efficient membership testing. The lemma appears again in 47.02.01 where NP-completeness plays an analogous role to non-context-freeness — proving that certain problems lie outside a complexity class. The generalises from the regular pumping lemma of 47.01.04 by replacing the state-sequence pigeonhole argument with a parse-tree pigeonhole argument, and putting these together gives the full picture of how structural properties of grammars constrain the languages they generate.

Full proof set Master

Proposition 1 (CFL pumping lemma). If $L$ is a CFL, then the pumping lemma conditions hold.

Proof. Let $G = (V, Σ, R, S)$ be a CFG in CNF generating $L ∖ {ε}$ with $∣ V ∣ = k$ . Set $p = 2^{k}$ . For $s \in L$ with $∣ s ∣ \geq p$ , consider a parse tree for $s$ . The yield of a subtree of height $h$ has length at most $2^{h - 1}$ (each internal node has exactly 2 children in CNF). Since $∣ s ∣ \geq 2^{k}$ , the height is at least $k + 1$ , so the longest root-to-leaf path has at least $k + 1$ internal nodes with nonterminal labels. By pigeonhole, some $A \in V$ appears at least twice.

Let the upper occurrence of $A$ be at node $n_{1}$ and the lower at $n_{2}$ . The subtree at $n_{1}$ has yield $v x y$ and the subtree at $n_{2}$ has yield $v$ (or $v y$ , depending on position). Since $n_{2}$ is a proper descendant of $n_{1}$ and $G$ has no unit productions in CNF, $∣ v y ∣ > 0$ . The path from $n_{1}$ to $n_{2}$ uses at most $k + 1$ nonterminals, so the subtree at $n_{1}$ has height at most $k + 1$ , giving $∣ v x y ∣ \leq 2^{k} = p$ .

For any $i \geq 0$ , the derivation $A \Rightarrow^{*} v A y$ (from $n_{1}$ 's expansion to $n_{2}$ ) can be iterated $i$ times to get $A \Rightarrow^{*} v^{i} A y^{i}$ . This produces a valid derivation of $u v^{i} x y^{i} z$ . $□$

Proposition 2 (CYK correctness). After running CYK on input $w = a_{1} \dots a_{n}$ with CNF grammar $G$ , $S \in T [1, n]$ if and only if $w \in L (G)$ .

Proof. By induction on span length $ℓ = j - i + 1$ . Base $ℓ = 1$ : $A \in T [i, i]$ iff $A \to a_{i} \in R$ iff $A \Rightarrow^{*} a_{i}$ . Inductive step: $A \in T [i, j]$ iff $\exists k$ with $A \to B C \in R$ , $B \in T [i, k]$ , $C \in T [k + 1, j]$ . By induction, $B \Rightarrow^{*} a_{i} \dots a_{k}$ and $C \Rightarrow^{*} a_{k + 1} \dots a_{j}$ . So $A \Rightarrow B C \Rightarrow^{*} (a_{i} \dots a_{k}) (a_{k + 1} \dots a_{j})$ . Conversely, if $A \Rightarrow^{*} a_{i} \dots a_{j}$ with $ℓ > 1$ , the first production step must be $A \to B C$ (CNF), and the yield splits at some $k$ with $B \Rightarrow^{*} a_{i} \dots a_{k}$ and $C \Rightarrow^{*} a_{k + 1} \dots a_{j}$ . By induction, $B \in T [i, k]$ and $C \in T [k + 1, j]$ , so $A \in T [i, j]$ . $□$

Connections Master

47.01.04 — The regular pumping lemma is the structural precursor: one pumpable region from DFA state repetition versus two from parse-tree nonterminal repetition.
47.01.05 — Context-free grammars and pushdown automata define the CFL class; the pumping lemma and CYK algorithm provide the analytical and algorithmic tools for working with this class.
47.02.01 — The P-vs-NP question mirrors the regular-vs-CFL containment question: both ask whether a richer computational model solves problems that a weaker one cannot.
47.02.05 — Space complexity provides another hierarchy where pumping-style arguments (via the space hierarchy theorem) prove strict separations between complexity classes.
40.04.01 — Graph-theoretic parsing methods (such as parse-forest intersection and shared parse forests) use the same dynamic-programming structure as CYK.

Historical & philosophical context Master

The context-free pumping lemma was proved by Bar-Hillel, Perles, and Shamir in 1961 as part of their systematic study of phrase-structure grammars. Their paper "On Formal Properties of Simple Phrase Structure Grammars" established both the pumping lemma and several closure properties of CFLs ^{[Sipser §2.3]}.

The CYK algorithm is named after Cocke, Younger, and Kasami, who discovered it independently. Younger (1967) proved that context-free language recognition can be done in $O (n^{3})$ time using dynamic programming. Kasami described a similar algorithm in an internal technical report (1965). The connection to Chomsky normal form as the enabling preprocessing step was made explicit by Hopcroft and Ullman (1969).

Ogden's lemma (1968) strengthened the pumping lemma by introducing the concept of "distinguished positions," resolving several open questions about the boundaries of the CFL class. William Ogden's paper "A Helpful Result for Proving inherent Ambiguity" showed that the language ${a^{i} b^{j} c^{k} : i = j or j = k}$ is inherently ambiguous (every grammar for it is ambiguous), using his strengthened lemma as a key tool.

Parikh's theorem (1966) revealed a deep algebraic property of CFLs: their commutative image is always semilinear. This connected formal language theory to the theory of Presburger arithmetic and showed that the "counting" power of CFLs is fundamentally limited.

Bibliography Master

@book{sipser2013,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2013},
}
@book{hopcroft2006,
  author    = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
  title     = {Introduction to Automata Theory, Languages, and Computation},
  edition   = {3rd},
  publisher = {Pearson},
  year      = {2006},
}
@article{barhillel1961formal,
  author  = {Bar-Hillel, Yehoshua and Perles, Micha and Shamir, Eli},
  title   = {On Formal Properties of Simple Phrase Structure Grammars},
  journal = {Zeitschrift f\"ur Phonetik, Sprachwissenschaft und Kommunikationsforschung},
  volume  = {14},
  pages   = {143--172},
  year    = {1961},
}
@article{ogden1968helpful,
  author  = {Ogden, William},
  title   = {A Helpful Result for Proving Inherent Ambiguity},
  journal = {Mathematical Systems Theory},
  volume  = {2},
  number  = {3},
  pages   = {191--194},
  year    = {1968},
}
@article{youngers1967recognition,
  author  = {Youngers, Daniel H.},
  title   = {Recognition and Parsing of Context-Free Languages in Time $n^3$},
  journal = {Information and Control},
  volume  = {10},
  number  = {2},
  pages   = {189--208},
  year    = {1967},
}

Prerequisites

47.01.05 pending

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §2.3 (the pumping lemma for context-free languages: long enough strings in a CFL have two pumpable regions)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §2.3 and §2.4 (formal CFL pumping lemma via parse-tree structure, CYK algorithm for membership in $O (n^{3})$ time)
master: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §2.3-2.4; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §7.4 (CYK with Chomsky normal form conversion, Ogden's lemma as a strengthening)

References

Sipser, M. — Introduction to the Theory of Computation (3rd ed.) · Cengage (2013). Section 2.3 states the pumping lemma for context-free languages: if $L$ is context-free, then there exists $p$ such that every $s \in L$ with $∣ s ∣ \geq p$ can be divided as $s = uv x y z$ with (1) for each $i \geq 0$ , $u v^{i} x y^{i} z \in L$ , (2) $∣ v y ∣ > 0$ , and (3) $∣ v x y ∣ \leq p$ ; the proof uses the fact that in a parse tree of height $h$ for a grammar in Chomsky normal form, the yield has length at most $2^{h - 1}$ , so a sufficiently long string forces a repeated nonterminal on some path, creating two pumpable regions $v$ and $y$ . Section 2.4 presents the CYK algorithm for deciding membership in a CFL in $O (n^{3})$ time using dynamic programming on substrings of the input.
Hopcroft, J. E., Motwani, R. & Ullman, J. D. — Introduction to Automata Theory, Languages, and Computation (3rd ed.) · Pearson (2006). Section 7.4 develops the CYK algorithm in detail: convert the grammar to Chomsky normal form (CNF) where every production is either $A \to B C$ or $A \to a$ , then fill a triangular table where entry $T [i, j]$ is the set of nonterminals deriving the substring $a_{i} \dots a_{j}$ ; the algorithm runs in $O (n^{3} \cdot ∣ G ∣)$ time where $∣ G ∣$ is the grammar size. Ogden's lemma is presented as a strengthening that marks certain positions as distinguished, forcing the pumpable regions to include distinguished positions.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m