CYK Membership Test for the String “baaba”

This lesson applies the CYK algorithm to the grammar

$$\begin{aligned} S &\to AB \mid BC\\ A &\to BA \mid a\\ B &\to CC \mid b\\ C &\to AB \mid a \end{aligned}$$

and the input string

$$w=\text{baaba}.$$

The goal is to determine whether $w\in L(G)$. CYK is a bottom-up parsing method that fills a triangular chart of substrings. It normally requires Chomsky Normal Form; this grammar already satisfies that requirement because every production is either binary or produces one terminal.

CYK records every nonterminal capable of deriving each contiguous substring. The final cell contains the answer: if it includes $S$, the string is generated by the grammar.

Footnotes

1. CYK algorithm - Wikipedia - Describes CYK as a bottom-up dynamic-programming parser requiring CNF-style grammar rules. ↩

CYK chart notation

Let $T[i,j]$ denote the set of nonterminals that derive the substring beginning at position $i$ and ending at position $j$, using one-based indexing.

For example:

• $T[1,1]$ describes the substring $\text{b}$.
• $T[2,4]$ describes the substring $\text{aab}$.
• $T[1,5]$ describes the complete string $\text{baaba}$.

For a substring of length greater than one, CYK tries every split point:

$$w[i:j]=w[i:k]\;w[k+1:j].$$

If a production $X\to YZ$ exists, and

$$Y\in T[i,k] \qquad\text{and}\qquad Z\in T[k+1,j],$$

then $X$ is inserted into $T[i,j]$.

Footnotes

1. Parsing I: Context-Free Grammars and the CYK Algorithm - Explains chart cells, binary splits, and the CYK recurrence. ↩

Step 1: Length-one substrings

The terminal productions are

$$A\to a,\qquad C\to a,\qquad B\to b.$$

The input positions are:

Thus,

$$\begin{aligned} T[1,1]&=\{B\}\\ T[2,2]&=\{A,C\}\\ T[3,3]&=\{A,C\}\\ T[4,4]&=\{B\}\\ T[5,5]&=\{A,C\}. \end{aligned}$$

Step 2: Length-two substrings

For each length-two substring, there is only one split.

Substring $w_1w_2=\text{ba}$

The split is

$$\text{b}\mid\text{a}.$$

The left cell contains $\{B\}$ and the right cell contains $\{A,C\}$. Therefore, the possible pairs are

$$(B,A),\qquad (B,C).$$

The grammar contains $A\to BA$, but no rule $X\to BC$. Hence,

$$T[1,2]=\{A\}.$$

Indeed,

$$A\Rightarrow BA\Rightarrow ba.$$

Substring $w_2w_3=\text{aa}$

The possible pairs are

$$(A,A),\ (A,C),\ (C,A),\ (C,C).$$

The only matching binary rule is

$$B\to CC.$$

Therefore,

$$T[2,3]=\{B\}.$$

Substring $w_3w_4=\text{ab}$

The left cell is $\{A,C\}$ and the right cell is $\{B\}$. The possible pairs are

$$(A,B),\qquad (C,B).$$

The rules $S\to AB$ and $C\to AB$ match $(A,B)$. Thus,

$$T[3,4]=\{S,C\}.$$

Substring $w_4w_5=\text{ba}$

This has the same symbol pattern as positions $1$–$2$:

$$T[4,5]=\{A\}.$$

The length-two results are therefore

$$\boxed{ T[1,2]=\{A\},\quad T[2,3]=\{B\},\quad T[3,4]=\{S,C\},\quad T[4,5]=\{A\}. }$$

Step 3: Length-three substrings

Substring $w_1w_3=\text{baa}$

There are two splits.

Split 1: $\text{b}\mid\text{aa}$

The pair is

$$(B,B).$$

No production has right-hand side $BB$.

Split 2: $\text{ba}\mid\text{a}$

The pair combinations are

$$(A,A),\qquad (A,C).$$

No production has right-hand side $AA$ or $AC$.

Therefore,

$$T[1,3]=\varnothing.$$

Substring $w_2w_4=\text{aab}$

Split 1: $\text{a}\mid\text{ab}$

The left cell is $\{A,C\}$ and the right cell is $\{S,C\}$. The possible pairs include

$$(A,S),\ (A,C),\ (C,S),\ (C,C).$$

The rule $B\to CC$ matches only if the left side contains $C$ and the right side contains $C$. Hence,

$$B\in T[2,4].$$

Split 2: $\text{aa}\mid\text{b}$

The pair is

$$(B,B),$$

which matches no binary production.

Thus,

$$T[2,4]=\{B\}.$$

Substring $w_3w_5=\text{aba}$

Split 1: $\text{a}\mid\text{ba}$

The pair combinations are

$$(A,A),\qquad (C,A).$$

Neither matches a binary production.

Split 2: $\text{ab}\mid\text{a}$

Since $T[3,4]=\{S,C\}$ and $T[5,5]=\{A,C\}$, the pair $(C,A)$ is possible, but no rule has right-hand side $CA$.

Therefore,

$$T[3,5]=\varnothing.$$

The length-three cells are

$$\boxed{ T[1,3]=\varnothing,\quad T[2,4]=\{B\},\quad T[3,5]=\varnothing. }$$

Step 4: Length-four substrings

Substring $w_1w_4=\text{baab}$

Split 1: $\text{b}\mid\text{aab}$

The pair is

$$(B,B).$$

No rule matches $BB$.

Split 2: $\text{ba}\mid\text{ab}$

The cells are

$$T[1,2]=\{A\}, \qquad T[3,4]=\{S,C\}.$$

The possible pairs are $(A,S)$ and $(A,C)$; neither occurs on the right-hand side of a binary production.

Split 3: $\text{baa}\mid\text{b}$

Since $T[1,3]=\varnothing$, this split contributes nothing.

Therefore,

$$T[1,4]=\varnothing.$$

Substring $w_2w_5=\text{aaba}$

Split 1: $\text{a}\mid\text{aba}$

Since $T[3,5]=\varnothing$, this split contributes nothing.

Split 2: $\text{aa}\mid\text{ba}$

The cells are

$$T[2,3]=\{B\}, \qquad T[4,5]=\{A\}.$$

The pair is $(B,A)$, which matches

$$A\to BA.$$

Therefore,

$$T[2,5]=\{A\}.$$

Split 3: $\text{aab}\mid\text{a}$

The cells are $\{B\}$ and $\{A,C\}$, giving $(B,A)$ and $(B,C)$. Again, only $BA$ matches, so this split also derives $A$.

Thus,

$$T[2,5]=\{A\}.$$

The length-four cells are

$$\boxed{ T[1,4]=\varnothing,\qquad T[2,5]=\{A\}. }$$

Step 5: Length-five substring

The complete input is

$$w_1w_5=\text{baaba}.$$

There are four possible split points.

The first split derives $A$:

$$T[1,1]=\{B\},\qquad T[2,5]=\{A\},$$

and because

$$A\to BA,$$

we obtain

$$A\in T[1,5].$$

No split produces $S$:

• $S\to AB$ would require a split whose left cell contains $A$ and whose right cell contains $B$.
• $S\to BC$ would require a split whose left cell contains $B$ and whose right cell contains $C$.

Neither condition is satisfied.

Hence,

$$T[1,5]=\{A\}.$$

Complete CYK triangular table

The table is conventionally displayed with longer substrings above shorter substrings.

A positional triangular representation is:

The top-right cell is

$$T[1,5]=\{A\}.$$

Conclusion

The CYK algorithm returns

$$\boxed{\text{baaba}\notin L(G)}.$$

Although the entire string can be derived from nonterminal $A$,

$$A\Rightarrow BA \Rightarrow bA \Rightarrow bB A \Rightarrow baaba,$$

this does not establish membership in $L(G)$ because the grammar’s designated start symbol is $S$, not $A$.

A valid derivation from the grammar must have the form

$$S\Rightarrow^* \text{baaba}.$$

Since $S\notin T[1,5]$, no such derivation exists.