Removing null productions from a context free grammar

1.6k views Asked by At
X -> zZ|yW|WW
Y->Z
Z->X|ε
W->Y|X

Would I be right to think that as Y only Z as its terminal the ε moves to Y giving:

X -> zZ|yW|WW
Y->Z|ε
Z->X
W->Y|X

then?

X -> zZ|yW|WW|z
Y->Z
Z->X
W->Y|X
1

There are 1 answers

0
Brian Tompsett - 汤莱恩 On

You missed the propagation of ε from Y in the w production.

X -> zZ|yW|WW|z
Y->Z
Z->X
W->Y|X|ε

which then moves up:

X -> zZ|yW|WW|z|y|ε
Y->Z
Z->X
W->Y|X

and continues:

X -> zZ|yW|WW|z|y
Y->Z
Z->X|ε
W->Y|X|ε

and we are back we are we started! This grammar can never be written without ε.

(Unless someone wants to correct me?)