CFG to CNF - unary/associative operators

[mr_m4x]

Homework Statement

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.

Homework Equations

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!

 

[KataKoniK]

Hello,

To convert your grammar into Chomsky normal form, you will need to use some additional variables and productions. First, let's deal with the unary operators. To convert them, you can use the following productions:

S -> S'
S' -> 0|1|a|b|S+S|S.S
S' -> S''

S'' -> S*
S'' -> (S)

This will allow you to represent the unary operators as separate variables, while still following the rules of CNF.

Next, you will need to eliminate the productions with more than two variables on the right-hand side. To do this, you can use the following productions:

S -> S'
S' -> S''S''' | S+S | S.S
S''S''' -> S''S''
S''S''' -> S*S*
S''S''' -> (S+S)*(S+S)
S''S''' -> (S.S)*(S.S)

This will allow you to represent the binary operators as separate variables, while still following the rules of CNF.

Finally, you will need to eliminate the productions with terminals on the right-hand side. To do this, you can use the following productions:

S -> S'
S' -> T
T -> 0 | 1 | a | b

This will allow you to represent the terminals as separate variables, while still following the rules of CNF.

Overall, your converted grammar will look like this:

S' -> S

S -> S''S'''
S' -> S+S | S.S
S''S''' -> S''S''
S''S''' -> S*S*
S''S''' -> (S+S)*(S+S)
S''S''' -> (S.S)*(S.S)

S'' -> S*
S'' -> (S)

S -> T
T -> 0 | 1 | a | b

I hope this helps! Let me know if you have any further questions.

 

[Mene]

Your approach to add a new start symbol is correct. To handle the unary operators, you can replace them with new variables and add corresponding productions. For example, for the unary operator *, you can add a new variable X and the production X -> S*. This will result in the following productions:

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

Similarly, you can handle the unary operator () by adding a new variable Y and the production Y -> (S). Your final set of productions will then look like this:

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

This set of productions satisfies the requirements of CNF, as all productions have two variables on the RHS, except for the production S' -> S. You can further simplify this by replacing the variable X and Y with a new variable Z, resulting in the following set of productions:

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

This set of productions is now in CNF and represents the original context-free grammar in Chomsky's normal form.