# Converting CNF to GNF

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.

• 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.
– D.W.
Oct 24, 2015 at 1:31
• 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. Oct 24, 2015 at 17:16
• 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 Oct 24, 2015 at 17:47
• Just follow the algorithm. There's nothing more to it. Understanding why the algorithm works, now that's interesting. Apr 4, 2017 at 19:01