[Solved]: Convert a CFG into CNF

Problem Detail: 

I'm still new to CFG and CNF and have trouble sometimes understanding the concepts.

I'm trying to convert this CFG into Chomsky Normal Form:

G: S -> aSbS | bSaS | epsilon 

I think the language generates all strings with same number of a and b, i.e. {a^n b^n |n>-0}.

But to convert it into CNF, I've finished adding a new start state and eliminating epsilon-productions:

S_0 -> S | epsilon S -> aSbS | bSaS | aS | bS | a | b 

Perhaps I need two non-terminals(variables) A -> a and B -> b :

S_0 -> S | epsilon S -> ASBS | BSAS | AS | BS | a | b A -> a B -> b 

I'm stuck here and really don't know what the next step should be. There seem to be no unit productions or useless symbols.

Asked By : Megumi

Answered By : TLW

Wikipedia has a good breakdown of how to convert to CNF.

Your first steps are correct, if incomplete: you should have the following:

S_0 -> S | epsilon S -> ASBS | BSAS | AS | BS | A | B A -> a B -> b 

(Notice the S rule.)

The next thing you need to do is decompose your S state(s) into multiple states, each with two or less nonterminals:

S -> T | W | AS | BS | A | B T -> AU U -> SV V -> BS W -> BX X -> SY Y -> AS 

Does this get you unstuck?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48267

3.2K people like this

 Download Related Notes/Documents