# Grammar to Chomskys Normal Form eliminating epsilon productions

I've got the following grammar I'm attempting to convert to CNF.

S -> T01 | USV | epsilon
U -> X
V -> S1S | X | 1
X -> 0XS | 0
T -> TV | XT | UTU


I know that when I eliminate epsilon-productions I get...

S -> T01 | USV | UV
U -> X
V -> S1S | S1 | 1S | X | 1
X -> 0XS | 0X | 0
T -> TV | XT | UTU


I understand that we're getting rid of the epsilon but I don't really get what we're doing with the other symbols. For example how does S now produce UV? If someone could explain this to me I'd really appreciate it.

-
Is there an algorithm to remove epsilon productions from a grammar??..if there is ca you plz reply asap... – user67008 Mar 16 '13 at 17:26

Here's how $S$ produces $UV$: $S \rightarrow USV \rightarrow UV$.

Generalizing the example, whenever a non-terminal $X$ produces $\epsilon$, whenever we see $X$ on the right-hand side we can (optionally) delete it. This is more-or-less what the epsilon-elimination algorithm is trying to do.

I suggest that instead of trying to follow the algorithm blindly, you try to understand what it's doing. You need to understand three things:

1. Why the transformations employed by the algorithm do not change the language.

2. Why the algorithm eventually gets rid of all epsilon productions.

3. Why the algorithm terminates.

-
Thanks. Just as a side question... why is T a non generating state and S isn't? – Ulkmun Jan 15 '11 at 16:10
Another side algorithm recovers all non-terminals that can produce epsilon. The idea is to start with the explicit epsilon productions, and "go back" to implicit epsilon derivations. You can try inventing the algorithm yourself. – Yuval Filmus Jan 15 '11 at 16:56