The CYK parsing table and span variables

Let $G=(V,\mathrm{\Sigma },P,S)$ be a grammar in Chomsky normal form, and let $w=a_1\cdots a_n$ be a nonempty word over $\mathrm{\Sigma }$.

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

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

and, for $\mathrm{\ell }\ge 2$,

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

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

• The definition uses only the CNF production types $A\to a$ and $A\to BC$.

• The top cell $T[1,n]$ corresponds to the whole input word.

For a word of length $4$, the following triangle displays every valid cell. The outlined cells pick out the split $i=1$, $\mathrm{\ell }=4$, $k=2$; they do not assert that the corresponding sets are nonempty.

In this split, $T[1,2]$ covers $a_1{a}_2$ and $T[3,2]$ covers $a_3{a}_4$. If $A\to BC\in P$, $B\in T[1,2]$, and $C\in T[3,2]$, the defining recurrence places $A$ in $T[1,4]$. In general, the two child intervals end at $i+k-1$ and begin at $i+k$, respectively, so they are adjacent and partition the parent interval from $i$ to $i+\mathrm{\ell }-1$. This illustration only explains the indexing; the definition does not depend on it.