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. Oct 24 '15 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 Oct 24 '15 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 Oct 24 '15 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 Apr 4 '17 at 19:01

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.