Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Transform Grammer to Chomsky Normal Form

  1. Oct 20, 2009 #1
    Can anyone help me transform the following G to Chomsky Normal Form?

    S --> abAB

    A --> bAB | λ

    B --> BAa | A | λ

    Thanks for your help!
  2. jcsd
  3. Oct 25, 2009 #2
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook