grammarcontext-free-grammarleft-recursionautomata-theory

Can epsilon production be assumed in a left recursive grammar

I have a grammar:

S->Sa|Sb

I want to know if I can assume S->e as a production in the grammar?

I.e.,

Is S->Sa|Sb is the same as S->Sa|Sb|e ?

e = null string (epsilon)

I am trying to understand removal of left recursion and I came across this question.

Solution

  • Unless whoever provided the grammar said that you can assume S -> e, then no, you can't assume productions that don't appear in a grammar.

    Of course, this means that there's no way for a derivation from S to terminate. Which means that it doesn't derive any sentences, which means that the language of the grammar is the empty set. This is 'allowed', but is unusual in practice.

    More likely, it's a mistake in the grammar.