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:run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can derive the word $baabb$ from the context.write the left derivation. My try:$1.$$$\begin{array}{c|lcr}i\bigg/j &  1 & 2 & 3 &  4 & 5 \\\hline1 & \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}$$$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?
Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$
algorithms;context free;formal grammars;parsers
Watch this video and you should get:$$\begin{array}{c|lcr}i\bigg/j &  1 & 2 & 3 &  4 & 5 \\\hline1 & \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