DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 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.

The CYK parsing table and span variables

Definition

Let $G = (V, Σ, P, S)$ be a grammar in Chomsky normal form, and let $w = a_{1} \dots a_{n}$ be a nonempty word over $Σ$ .

The CYK table of $G$ on $w$ is the triangular array of sets $T [i, ℓ] \subseteq V$ defined for $1 \leq i \leq n$ and $1 \leq ℓ \leq n - i + 1$ by:

$T [i, 1] : = {A \in V : A \to a_{i} is a production of G},$

and, for $ℓ \geq 2$ ,

$T [i, ℓ] : = {A \in V : \exists k (1 \leq k < ℓ) and A \to B C \in P with B \in T [i, k], C \in T [i + k, ℓ - k]} .$

When $A \in T [i, ℓ]$ , we say that $A$ is a span variable for the substring $a_{i} \dots a_{i + ℓ - 1}$ .

Remarks

The definition uses only the CNF production types $A \to a$ and $A \to B C$ .
The top cell $T [1, n]$ corresponds to the whole input word.

Depends on

Used by

FALSE: CYK needs no normal-form preprocessing False statement
A variable lies in a CYK table cell exactly when it derives that span Lemma

Dependency tree · two levels

7 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)