Designing a context free grammar for a language; When to use the empty string

Question

$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 $

Answer 1

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.