Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$

With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$

I need to:

1. run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can derive the word $baabb$ from the context.

2. write the left derivation.

My try:

$1.$

$$\begin{array}{c|lcr} i\bigg/j & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \text{C,S} & \text{B} & \square& \square &\square \\ 2 & \quad\blacksquare & \text{A} & \text{A} & \square & \square \\ 3 & \quad\blacksquare & \quad\blacksquare & \text{A} & \text{S,B} & \square \\ 4 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} & \text{A,C} \\ 5 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} \\ \end{array}$$

1. $S\Longrightarrow BA \Longrightarrow CAA \Longrightarrow bAA\Longrightarrow bAACC\Longrightarrow baabb$

I'm stuck here in the table construction. How should I fill in the empty squares?

• The algorithm is very explicit. What specifically goes wrong when you try to follow the steps?
– Raphael
Dec 31 '15 at 17:53

$$\begin{array}{c|lcr} i\bigg/j & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \text{C,S} & \text{B} & \text{B,S} & \text{A,B,C} & \text{B,C,\color{red}{\text{S}},A} \\ 2 & \quad\blacksquare & \text{A} & \text{A} & \text{B,C,A,S} & \text{A,B,C} \\ 3 & \quad\blacksquare & \quad\blacksquare & \text{A} & \text{S,B} & \text{A,S,C} \\ 4 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} & \text{A,C} \\ 5 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} \\ \end{array}$$
Since S is in the left and higher corner so we can derivate the word $baabb$ from the context