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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Transform Grammer to Chomsky Normal Form