Grammar to Chomskys Normal Form eliminating epsilon productions

Question

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.

Answer 1

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.