CODEWITHSUNDEEP
grammarcontext-free-grammarleft-recursionautomata-theory
Vedant Jumle
Vedant Jumle

Reputation: 35

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.

Upvotes: -1

Views: 100

Answers (1)

Michael Dyck
Michael Dyck

Reputation: 2413

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.

Upvotes: 1

Related Questions