2
$\begingroup$

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?

$\endgroup$
  • $\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 Nov 14 '15 at 21:43
5
$\begingroup$

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.

$\endgroup$
  • $\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$ – user3606704 Nov 14 '15 at 20:36
  • $\begingroup$ This grammar shows that it's better not to allow $S$ on the right side at all. $\endgroup$ – Yuval Filmus Nov 14 '15 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$ – Yuval Filmus Nov 14 '15 at 20:38
  • $\begingroup$ I'd hardly call it a hack. How else would you efficiently define a regular grammar for $(aa)^*$? $\endgroup$ – Rick Decker Nov 15 '15 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$ – Yuval Filmus Nov 15 '15 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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