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 contextfree 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 0 , making S 0 the
start variable, and adding to P the productions
S 0 → S|λ
generates L. Therefore, any nontrivial conclusion we can make for L – {λ} will
almost certainly transfer to L. Also, given any context-free grammar G, there is a
method for obtaining such that
(see Exercises 13 and 14
at the end of this section). Consequently, for all practical purposes, there is no
difference between context-free languages that include λ and those that do not.
For the rest of this chapter, unless otherwise stated, we will restrict our
discussion to λ-free languages.
A Useful Substitution Rule
Many rules govern generating equivalent grammars by means of substitutions.
Here we give one that is very useful for simplifying grammars in various ways.
We will not define the term simplification precisely, but we will use it
nevertheless. What we mean by it is the removal of certain types of undesirable
productions; the process does not necessarily result in an actual reduction of the
number of rules.
Theorem 6.1
Let G = (V, T, S, P) be a context-free grammar. Suppose that P contains a
production of the form
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 contextfree 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 0 , making S 0 the
start variable, and adding to P the productions
S 0 → S|λ
generates L. Therefore, any nontrivial conclusion we can make for L – {λ} will
almost certainly transfer to L. Also, given any context-free grammar G, there is a
method for obtaining such that
(see Exercises 13 and 14
at the end of this section). Consequently, for all practical purposes, there is no
difference between context-free languages that include λ and those that do not.
For the rest of this chapter, unless otherwise stated, we will restrict our
discussion to λ-free languages.
A Useful Substitution Rule
Many rules govern generating equivalent grammars by means of substitutions.
Here we give one that is very useful for simplifying grammars in various ways.
We will not define the term simplification precisely, but we will use it
nevertheless. What we mean by it is the removal of certain types of undesirable
productions; the process does not necessarily result in an actual reduction of the
number of rules.
Theorem 6.1
Let G = (V, T, S, P) be a context-free grammar. Suppose that P contains a
production of the form