TheEagle
TheEagle

Reputation: 117

Chomsky Normal Form Rules

In this old exam-question I need to convert a grammar to CNF, but I suspect the provided solution is wrong.

Grammar:

S -> aAB|a|aA|aB|AbB|b|Ab|bB
A -> aA|a|cC|c
B -> bB|b|dD|d
C -> cC|c
D -> dD|d

In the first step I set variables for the four terminals:

V -> a
X -> b
Y -> c
Z -> d

In the second step I replace the terminals with the variables(only the productions in S for now):

S -> VAB|a|VA|VB|AXB|AX|XB

In the third step I replace AB in VAB with U -> AB so I get:

S -> VU|a|VA|VB|AXB|AX|XB

In the solution, I don't understand what's happening with the S-productions AbB and bB(which I have set to AXB and XB). This is the provided answer for the S-productions:

S → VU|a|VA|VB|UX|b|AX|BX

How come AbB is set to UX and bB to BX? Should not bB be set to XB at least?

Upvotes: 0

Views: 137

Answers (0)

Related Questions