Transform Grammer to Chomsky Normal Form

  • Context: Undergrad 
  • Thread starter Thread starter jferg449
  • Start date Start date
  • Tags Tags
    Form Normal Transform
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 6K views
jferg449
Messages
1
Reaction score
0
Can anyone help me transform the following G to Chomsky Normal Form?

S --> abAB

A --> bAB | λ

B --> BAa | A | λ


Thanks for your help!
 
Physics news on Phys.org
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.