Converting grammar to Chomsky Normal Form?

Question

Convert the grammar below into Chomsky Normal Form. Give all the intermediate steps.

S -> AB | aB
A -> aab|lambda
B -> bbA

Ok so the first thing I did was add a new start variable S0

so now I have

S0 -> S
S -> AB | aB
A -> aab|lambda
B -> bbA

then I removed all of the lambda rules:

S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb

Then I checked for S->S and A->B type rules which did not exist. And that was the answer I came up with, do I need to do anything further or did I do anything wrong?

Answer 1

Without getting into too much theory and proofs(you could look at this in Wikipedia), there are a few things you must do when converting a Context Free Grammar to Chomsky Normal Form, you generally have to perform four Normal-Form Transformations. First, you need to identify all the variables that can yield the empty string(lambda/epsilon), directly or indirectly - (Lambda-Free form). Second, you need to remove unit productions - (Unit-Free form). Third, you need to find all the variables that are live/useful (Usefulness). Four, you need to find all the reachable symbols (Reachable). At each step you might or might not have a new grammar. So for your problem this is what I came up with...

---

Context-Free Grammar

G(Variables = { A B S }
Start = S 
Alphabet = { a b lamda}

Production Rules = { 
S  ->  |  AB  |  aB  |  
A  ->  |  aab  |  lamda  |  
B  ->  |  bbA  |   } )

Remove lambda/epsilon

ERRASABLE(G) = { A }

G(Variables = { A S B }
Start = S
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  B  | 
B  ->  |  bbA  |  bb  |   } )

Remove unit produtions

UNIT(A) { A }
UNIT(B) { B }
UNIT(S) { B S }
G (Variables = { A B S }
Start = S 
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  bb  |  bbA  |  
A  ->  |  aab  |  
B  ->  |  bbA  |  bb  |   })

Determine live symbols

LIVE(G) = { b A B S a }

G(Variables = { A B S }
Start = S
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  bb  |  bbA  |  
A  ->  |  aab  |  
B  ->  |  bbA  |  bb  |   })

Remove unreachable

REACHABLE (G) = { b A B S a }
G(Variables = { A B S }
Start = S 
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  bb  |  bbA  |  
A  ->  |  aab  |  
B  ->  |  bbA  |  bb  |   })

Replace all mixed strings with solid nonterminals

G( Variables = { A S B R I }
Start = S
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  RB  |  II  |  IIA  |  
A  ->  |  RRI  |  
B  ->  |  IIA  |  II  |  
R  ->  |  a  |  
I  ->  |  b  |   })

Chomsky Normal Form

G( Variables = { V A B S R L I Z }
Start = S 
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  RB  |  II  |  IV  |  
A  ->  |  RL  |  
B  ->  |  IZ  |  II  |  
R  ->  |  a  |  
I  ->  |  b  |  
L  ->  |  RI  |  
Z  ->  |  IA  |  
V  ->  |  IA  |   })