1
$\begingroup$

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.

  • 0
    Is there an algorithm to remove epsilon productions from a grammar??..if there is ca you plz reply asap...2013-03-16

1 Answers 1

2

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.

  • 0
    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 yoursel$f$.2011-01-15