Why is the start symbol "not allowed" on the right hand side in Chomsky normal form?

Question

I had a question regarding CNF (Chomsky normal form) in formal language theory.

I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow the start symbol to be on the right hand side of the production. However, I just can't wrap my head around why this is so.

In these cases, they put as the first step of converting a general context-free grammar into CNF to add the production

$$S_0 \rightarrow S$$

but I noticed that in some cases this actually leads to having one more unnecessary production, and in other cases it's impossible to completely remove the start symbol completely from the right hand side of productions (excluding the $S_0 \rightarrow S$ production). Also, the textbook that I'm using (Formal Languages and Automata, 6e - Peter Linz) allows the start symbol to be on the right side of a production.

What's the reason that this production is frowned upon?

Thank you.

Answer 1

Recall that in Chomsky normal form, we are allowed productions of three forms:

1. Productions of the form $A \to a$.
2. Productions of the form $A \to BC$.
3. The production $S \to \epsilon$.

We have to allow the production $S \to \epsilon$, since otherwise it will be impossible to generate the empty string.

Suppose for a moment that the production $S \to \epsilon$ is absent. Then we have the following very useful property:

If $A \Rightarrow^* w$ then $w \neq \epsilon$.

This comes up in some proofs of the pumping lemma, for example.

If we have the rule $S \to \epsilon$, then we no longer have the property above. However, a similar property holds:

If $A \Rightarrow^* w$ and $A \neq S$ then $w \neq \epsilon$.

This is due to our insistence of not having $S$ on the right-hand side of productions; otherwise we might have rules like $A \to SS$ and then derivations like $A \Rightarrow SS \Rightarrow^* \epsilon$.

If the rule $S \to \epsilon$ is absent, then there is no reason to disallow $S$ on the right-hand side of productions. Indeed, some authors allow $S$ on the right-hand side of productions as long as the production $S \to \epsilon$ is absent.

Answer 2

All these formalizations are proposed solutions for a problem that can be handled more elegantly. The production $S\to \varepsilon$ is only a trick to indicate that the empty string belongs to the language.

Here is the definition of "Chomsky normal form" as given by Chomsky ["On Certain Formal Properties of Grammars". Information and Control (1959) 137-167. doi:10.1016/S0019-9958(59)90362-6, open archive]. Note, sixty years ago, the meaning of "regular" was not yet fixed as we know it.

Definition 8. A grammar is regular if it contains only rules of the form $A\to a$ or $A\to BC$, where ... [additional restrictions omitted].

It is clear from this that Chomsky was not interested in languages that contained the empty string. And, if we want to have convenient derivations for strings in a grammar it certainly is not very inconventient to have just a single string $\varepsilon$ that has no derivation?

So, as a Lemma, Chomsky's normal form would be stated like this, if we want to leave inclusion of the empty string open.

Lemma. For every context-free language $L$ there exists a grammar $G$ in Chomsky normal form, such that $L(G) = L -\{\varepsilon\}$.