I have to convert a grammar to Chomsky normal form, the grammar is something like this
(not exactly but this is the important bit)
V → W
W → wWxXyYzZ | vXy | xX
X → xYZ | xY | xW | zZ
Y → xX | wW | wV | x
Z → yY | wW | wX | y | ϵ
I add the new start
S → V
V → X
W → wWxXyYzZ | vXy | xX
X → xYZ | xY | xW | zZ
Y → xX | wW | wV | x
Z → yY | wW | wX | y | ϵ
Remove nullables
S → V
V → X
W → wWxXyYzZ | vXy | xX | wWxXyYz
X → xYZ | xY | xW | zZ | xY | z
Y → xX | wW | wV | x
Z → yY | wW | wX | y
Remove unit variables
S → wWxXyYzZ | vXy | xX | wWxXyYz
V → wWxXyYzZ | vXy | xX | wWxXyYz
W → wWxXyYzZ | vXy | xX | wWxXyYz
X → xYZ | xY | xW | zZ | xY | z
Y → xX | wW | wV | x
Z → yY | wW | wX | y
When I am in this situation, It just feels strange to have 3 exactly the same.
I presume I can get rid of V because it can never be reached from the new start? I also take it that W needs to stay because it is referenced in the other variables?
Is there anything more I would need to do or do I move on to adding the variables to reduce everything to a reference to a single terminal or 2 variables.
Best Answer
You presume wrong - V is referenced by Y, which is referenced by S.
As far as I can see, you can in fact move on to adding variables now.