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$
$\endgroup$
1
-
$\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$– BrianONov 14, 2015 at 21:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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.
answered Nov 14, 2015 at 20:25
-
$\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$– SeekerNov 14, 2015 at 20:36
-
$\begingroup$ This grammar shows that it's better not to allow $S$ on the right side at all. $\endgroup$ 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$ 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$ 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$ Nov 15, 2015 at 21:54