I recently learned about the conversion, but I seem to be stuck.

I need to convert the following CFG to CNF:

$S → XY$

$X → abb|aXb|e$

$Y → c|cY$

  1. There is no S on the right side, so I did not need to add another
  2. I removed the null productions $X → e$




  1. I removed unit production $S→Y$ $Y→c$ with $S→c$

  2. There are no production rules which have more than 2 variables

  3. Here, I struggle. I am not allowed to have a terminal symbol and a variable together, but I am not sure how to get rid of these.

New grammar after step 4:





I managed to replace the symbol c with Z, and added the new rule, so that seems fixed. However, I am unsure what do do with $aXb$.

Is this okay so far? if yes, what step should i take next?

Thank you in advance!

| cite | improve this question | | | | |

Your Answer

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

Browse other questions tagged or ask your own question.