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?

  • $\begingroup$ 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.) $\endgroup$
    – Raphael
    Commented Jan 23, 2014 at 17:16
  • $\begingroup$ it is what written in a book.I DID NOT ARRIVE i just saw it.I want to know how it comes. $\endgroup$
    – techno
    Commented Jan 23, 2014 at 17:38
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Raphael
    Commented Jan 23, 2014 at 18:07
  • $\begingroup$ @Raphael LOL,The point is i do not understand it.Will you give me a break??? $\endgroup$
    – techno
    Commented Jan 24, 2014 at 4:07

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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