1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

CFG to CNF - unary/associative operators

  1. Mar 26, 2009 #1
    1. The problem statement, all variables and given/known data

    I'm trying to convert a context free grammar into Chomsky's normal form.

    These are the productions of my grammar:

    S -> 0|1|a|b|S+S|S.S|S*|(S)

    Where 0, 1, a, b are terminals, +, . are binary operators and *,() are unary operators.

    I know that for a grammar to be in CNF, all it's productions must be terminals or must have two and only two variables distinct of the start symbol.

    2. Relevant equations



    3. The attempt at a solution

    I added a new variable so I have removed the start symbol from the RHS of the productions, so now my productions look like this

    S' -> S

    S -> 0|1|a|b|S+S|S.S|S*|(S)

    Where S' is the new start symbol. Now my problem is that I'm not 100% sure about how to solve the two unary operators since nost of the RHS of the production complies with the requirements of a CNF.

    Maybe the solution looks like this...

    S -> 0|1|a|b|S+S|S.S|0*|1*|a*|b*|(S+S)*|(S.S)*|(0)|(1)|(a)|(b)|(S+S)|(S.S)

    ???

    Thanks!
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: CFG to CNF - unary/associative operators
Loading...