# Eliminating $\varepsilon$-productions during elimination of left recursion

I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any.

I have the grammar

$\qquad S \to Aa \mid b$
$\qquad A \to Ac \mid Sd \mid \varepsilon$

I can see after removing the epsilon productions the grammer becomes

$\qquad S \to Aa \mid a \mid b$
$\qquad A \to Ac \mid Sd \mid c \mid d$

I'm confused where the $a \mid b$ for $S$ and $c \mid d$ for $A$ come from. Can someone explain this?

• How is it you "can see" but not know where it comes from? How did you arrive at the new grammar? (Also, the new grammar generates $da$ which the old one does not.) – Raphael Jan 23 '14 at 17:16
• it is what written in a book.I DID NOT ARRIVE i just saw it.I want to know how it comes. – techno Jan 23 '14 at 17:38
• I'm sure the book contains the algorithm. Did you look for it? (And then you'd get that the result is wrong, as I stated.) – Raphael Jan 23 '14 at 18:07
• @Raphael LOL,The point is i do not understand it.Will you give me a break??? – techno Jan 24 '14 at 4:07

The idea of the algorithm is to first find out which non-terminals can produce $\epsilon$, and then eliminate them in all possible ways.
Finding out which non-terminals produce $\epsilon$. The idea here is to start with the set $X^{(0)}$ of non-terminals which have an $\epsilon$ production. We then construct the set $X^{(1)}$ which includes $X^{(0)}$ and all other non-terminals having productions in $X^{(0)*}$ (that is, have productions in which the right-hand side consists of non-terminals in $X^{(0)}$ only). Continue this way until the process stops. The final set $X$ consists of all non-terminals which could produce $\epsilon$.
For example, in your case $X = X^{(0)} = \{A\}$. If there was a production $S \to A$, then you would have $X^{(0)} = \{A\}$ and $X = X^{(1)} = \{A,S\}$.
Eliminating non-terminals which could produce $\epsilon$. Now we simply take all productions containing non-terminals in $X$, and eliminate these non-terminals in all possible ways. That is, for each production containing terminals in $X$, you add additional productions resulting from deleting some of the non-terminals in $X$, in all possible ways. If you get $\epsilon$ productions this way, you just remove them (unless it's the possibly allowed $S\to\epsilon$).
For example, in your case the affected productions are $S \to Aa$ and $A \to Ac$. Handling the first, you add the production $S \to a$, and handling the second, you add the production $A \to c$.