0
$\begingroup$

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?

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

Watch this video and you should get:

$$ \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

$\endgroup$
  • 2
    $\begingroup$ Please include the explanation provided in the video inside your answer. If the video goes down your answer has no use for future visitors. $\endgroup$ – orlp Dec 31 '15 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.