An Introduction to Formal Languages and Automata, 7th Edition

6.1 METHODS FOR TRANSFORMING GRAMMARS

We first raise an issue that is somewhat of a nuisance with grammars and languages in general: the presence of the empty string. The empty string plays a rather singular role in many theorems and proofs, and it is often necessary to give it special attention. We prefer to remove it from consideration altogether, looking only at languages that do not contain λ. In doing so, we do not lose generality, as we see from the following considerations. Let L be any context-free language, and let G = (V, T, S, P) be a context-free grammar for L−{λ}. Then the grammar we obtain by adding to V the new variable S₀, making S₀ the start variable, and adding to P the productions

$$S_0\to S|\lambda$$

generates L. Therefore, any nontrivial ...