LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-12

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A variable lies in a CYK table cell exactly when it derives that span

Statement

Let $G$ be a Chomsky-normal-form grammar, let $w = a_{1} \dots a_{n}$ be a nonempty word, and let $T [i, ℓ]$ be the CYK table of $G$ on $w$ . Then for every variable $A$ and every valid cell $(i, ℓ)$ , $A \in T [i, ℓ] if and only if A \Rightarrow_{G}^{*} a_{i} \dots a_{i + ℓ - 1} .$

Facts & Assumptions

Given: A CNF grammar $G$ , a nonempty word $w = a_{1} \dots a_{n}$ , and its CYK table.

[L1]

By The CYK parsing table and span variables, the cells $T [i, ℓ]$ are defined by terminal productions for $ℓ = 1$ and by binary productions $A \to B C$ together with a split point for $ℓ \geq 2$ .

[L2]

By One-step derivation and finite derivation in a context-free grammar, $A \Rightarrow_{G}^{*} u$ means that the sentential form $A$ derives the word $u$ by finitely many grammar steps.

Proof

technique · direct

1.1L1L2given

We induct on the span length $ℓ$ . For $ℓ = 1$ , [L1] says that $A \in T [i, 1]$ exactly when $A \to a_{i}$ is a production, and by [L2] that is exactly when $A \Rightarrow_{G}^{*} a_{i}$ .

2.1L1L2step 1.1induction

Assume the claim known for all shorter spans and let $ℓ \geq 2$ . If $A \in T [i, ℓ]$ , then [L1] provides a split $k$ and a production $A \to B C$ with $B \in T [i, k]$ and $C \in T [i + k, ℓ - k]$ . By the induction hypothesis, $B \Rightarrow_{G}^{*} a_{i} \dots a_{i + k - 1}$ and $C \Rightarrow_{G}^{*} a_{i + k} \dots a_{i + ℓ - 1}$ , so one use of $A \to B C$ followed by those derivations gives $A \Rightarrow_{G}^{*} a_{i} \dots a_{i + ℓ - 1}$ .

2.2L1L2step 1.1induction

Conversely, suppose $A \Rightarrow_{G}^{*} a_{i} \dots a_{i + ℓ - 1}$ with $ℓ \geq 2$ . Because $G$ is in CNF, the first derivation step from $A$ must be a binary production $A \to B C$ , and the derived word must split at some $k$ into a prefix from $B$ and a suffix from $C$ . The induction hypothesis then gives $B \in T [i, k]$ and $C \in T [i + k, ℓ - k]$ , so [L1] places $A$ in $T [i, ℓ]$ .

3.1step 1.1step 2.1step 2.2∎

Steps 1.1, 2.1, and 2.2 prove the equivalence for every cell.

Depends on

Used by

The CYK algorithm decides membership for CNF grammars Theorem

Dependency tree · two levels

6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Alfred V. Aho, COMS W3261 CS Theory, Lecture 10 (standard reference, not scraped)