Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.