I'm studying context free grammars and I can grasp how to create context free grammars given a set notation, and now to convert these context free grammars to Chomsky Normal form but I am utterly stumped on how to go past that and get to Greibach Normal Form, I am given the follow grammar which is already in Chomsky Normal Form:

S-> AB | BC

A -> AB | a

B -> AA | CB | b

C -> a | b

I know the basic idea of converting to GNF is to remove left recursion but I do not understand how to go about and do this.

  • 3
    $\begingroup$ Welcome to CS.SE! Where have you looked? Is the CNF->GNF conversion not covered in standard textbooks? I noticed that the Wikipedia page on GNF cites two papers that describe how to do the conversion, though the algorithms look fairly involved; have you checked them? This question cites one references that shows how to do the conversion, and this question seems to suggest a textbook that apparently has a description of how to do the conversion. $\endgroup$
    – D.W.
    Commented Oct 24, 2015 at 1:31
  • $\begingroup$ I saw those links on GNF and read through them but I still don't understand the types of rules that need to be replaced and what to replace them with. I can kind of tell that the rules A-> AB and the B rules have problems with GNF but I don't know how to fix these problems. $\endgroup$
    – Ramirez77
    Commented Oct 24, 2015 at 17:16
  • $\begingroup$ Okay I think I might have figured it out but would at least like some confirmation I did this correctly. I went through and got this as a GNF. S-> AB|BC, A-> aR1,B-> aR1A|CB|b, C->c|b, R1->BR1|B $\endgroup$
    – Ramirez77
    Commented Oct 24, 2015 at 17:47
  • $\begingroup$ Just follow the algorithm. There's nothing more to it. Understanding why the algorithm works, now that's interesting. $\endgroup$
    – Raphael
    Commented Apr 4, 2017 at 19:01

1 Answer 1


reduce the cfg into gnf S->aSb S-> ab


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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