Why a production rule $S\to ε$ has been included in the definition of regular grammar? In that case, why it is restricted for $S$ (start symbol) to be present on right hand side of any production rule?

  • $\begingroup$ It corresponds to the start state of a DFA or NFA being an accepting state: the empty string $\varepsilon$ is a member of the language. $\endgroup$
    – BrianO
    Commented Nov 14, 2015 at 21:43

1 Answer 1


This production rule allows the grammar to generate the empty string. We restrict it to the start symbol so that it can fulfill its function but not interfere with the properties of the grammar in any other way.

In short, it's a hack to allow regular grammars to generate the empty string.

  • $\begingroup$ What about the following grammar S->aS, S->ε. Start symbol is in right hand side of first rule. Is it not regular grammar? Still it generates a regular language. $\endgroup$
    – Seeker
    Commented Nov 14, 2015 at 20:36
  • $\begingroup$ This grammar shows that it's better not to allow $S$ on the right side at all. $\endgroup$ Commented Nov 14, 2015 at 20:37
  • $\begingroup$ Also, to some extent the definition is arbitrary. There are several variants that probably occur in the literature and define the same class of languages. $\endgroup$ Commented Nov 14, 2015 at 20:38
  • $\begingroup$ I'd hardly call it a hack. How else would you efficiently define a regular grammar for $(aa)^*$? $\endgroup$ Commented Nov 15, 2015 at 21:50
  • 1
    $\begingroup$ @RickDecker We both agree it's a worse hack. A better option would be to remove the empty string altogether, since it results in special cases in many proofs. Just as sometimes the natural numbers had better contain 0, and sometimes they had better not. $\endgroup$ Commented Nov 15, 2015 at 21:54

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.