$L= \{a^{2i}b^{j}vc^{j}(ac)^{i} | i,j \ge 0, v \in \{a,b\}^*\}$ over the alphabet $\Sigma = \{a,b,c\}$

How can a grammar be created from the language without the use of the empty string. Below is my example that does use the empty string.

$S \rightarrow aaSac|B$

$B \rightarrow bBc|C$

$C \rightarrow aC|bC|\epsilon $

  • $\begingroup$ Is it a requirement to create the grammar without empty string? $\endgroup$ – John L. Oct 30 '18 at 23:31
  • $\begingroup$ @Apass.Jack I am sort of confused about that. Given my information provided in the question, does anything state that the grammar needs to be created without the empty string? Do the alphabet of the language or the values that $v$ can have affect the presence of the empty string in the grammar? Is it even possible to create the grammar without the empty string. $\endgroup$ – SeesSound Oct 30 '18 at 23:33
  • $\begingroup$ If we assume, yes, there is a restriction on using $\epsilon$, then what would the grammar look like. $\endgroup$ – SeesSound Oct 30 '18 at 23:38
  • 1
    $\begingroup$ What do you mean by "a conceptualized Context-free Grammar"? I have never heard of that. Do you just mean "a Context-free Grammar"? $\endgroup$ – John L. Oct 30 '18 at 23:38
  • $\begingroup$ conceptualized is meant to mean, that I conceptualized the Grammar from the Language, that is, the grammar may have mistakes because it was created by me. Perhaps a different word would fit better. $\endgroup$ – SeesSound Oct 30 '18 at 23:41

You can use the empty string, $\epsilon$ liberally. It could help you conceptualize the grammar easier and faster. For example, as you said, because $v\in\{a,b\}^∗$ that v can be one of $a,b$ or $\epsilon$, therefore using $\epsilon$ will help you to isolate non-terminal symbol $v$ as generating all words over the alphabet $\{a,b\}$ using just three rules.

On the other hand, language $L$ in the question, $L= \{a^{2i}b^{j}vc^{j}(ac)^{i} | i,j \ge 0, v \in \{a,b\}^*\}$ can be generated by a context-free grammar without $\epsilon$ except one rule, $S\to\epsilon$. Here it is.

$S \rightarrow aaSac|B|aaac|\epsilon$
$B \rightarrow bBc|B|bc$
$C \rightarrow aC|bC|a|b$

You can obtain the above grammar by following the procedure to eliminate ε-rules, which can change any context-free grammar to an equivalent grammar that either does not use $\epsilon$ or just uses it once in the rule $S\to\epsilon$. Note that if the language includes the empty string, at least one usage of $\epsilon$ is inevitable; otherwise, it can only generate non-empty words. Finally, a grammar in Chomsky Normal form is designed to be such a grammar.

Just in case you might think every context-free grammar will use $\epsilon$ at least once, here is a grammar that does not use $\epsilon$.

$S\to a$.

In fact, for every grammar in Chomsky Normal form that uses $\epsilon$, you can remove that single rule, $S\to\epsilon$ to obtain a new grammar that does not use $\epsilon$. The languages generated by these two grammars are the same except the former one contains the empty string while the latter one does not.

| cite | improve this answer | |
  • $\begingroup$ Great answer, everything is well defined and easy to follow. Thanks! $\endgroup$ – SeesSound Oct 31 '18 at 3:37

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.