Transform Grammer to Chomsky Normal Form

[jferg449]

Can anyone help me transform the following G to Chomsky Normal Form?

S --> abAB

A --> bAB | λ

B --> BAa | A | λ


Thanks for your help!

 

[rasmhop]

Don't your textbook have some kind of algorithm for doing this? I know that my copy of "Introduction to the Theory of Computation" by Michael Sipser has one right after the definition of Chomsky normal form.

We first we split up rules to get (no need to introduce new start rule as S doesn't reference itself):

S -> abAB
A -> bAB
A -> λ
B -> BAa
B -> A
B -> λ

Then we remove B->A by adding B->u for every A->u where u is an arbitrary expression (no epsilon-rules to get rid of):

S -> abAB
A -> bAB
A -> λ
B -> BAa
B -> λ
B -> bAB
B -> λ

Now we replace rules with more than 2 symbols by simply splitting them up like a(b(c(de))) and we also add variables to represent the terminals.

S -> A'S1
S1 -> B'S2
S2 -> AB
A -> B'A1
A1 -> AB
A -> λ
B -> BB1
B1 -> AA'
B -> B'B2
B2 -> AB
B -> λ
A' -> a
B' -> b
λ' -> λ

Your book really should have an algorithm for doing this.