# Can I remove left recursion on this grammar

$S \rightarrow Sa \mid S \mid \epsilon$

This is a weird case where I have only one non-terminal. I'm trying to apply the algorithm 4.19 in the dragon book. It don't think it should be applicable but I think it gives something like that :

$S \rightarrow S'$

$S' \rightarrow aS \mid S' \mid \epsilon$

but this is equivalent to say

$S' \rightarrow aS' \mid S' \mid \epsilon$

Yes that is correct. Also you can safely remove $A\rightarrow A$ type of production rules. So the equivalent grammar is $S'\rightarrow aS'\ |\ \epsilon$.
Cycles are of the form $A\rightarrow B, B\rightarrow C, C\rightarrow A$. When we remove left recursion in immediate left recursive grammars, we are ignoring $S\rightarrow S$.
Also presence of $\epsilon$ creates problem for the algorithm 4.19 given in the red dragon book (2007 edition), but the method of removing left recursion in immediate left recursive grammar works even in the presence of $\epsilon$.
• It is weird that it works in a sense because it says in the book that I must not have a $\epsilon$ production nor a cycle but I have both so why do they say that then? – Maxime Roussin-Bélanger Feb 24 '16 at 23:36