1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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)


  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted