One kind of production that is sometimes undesirable is one in which the right
side is the empty string.
Definition 6.2
Any production of a context-free grammar of the form
A → λ
is called a λ-production. Any variable A for which the derivation
is possible is called nullable.
A grammar may generate a language not containing λ, yet have some λproductions or nullable variables. In such cases, the λ-productions can be
removed.
Example 6.4
Consider the grammar
with start variable S. This grammar generates the λ-free language {a n b n : n ≥ 1}.
The λ-production S 1 → λ can be removed after adding new productions obtained
by substituting λ for S 1 where it occurs on the right. Doing this we get the
grammar
We can easily show that this new grammar generates the same language as the
original one.
In more general situations, substitutions for λ-productions can be made in a
side is the empty string.
Definition 6.2
Any production of a context-free grammar of the form
A → λ
is called a λ-production. Any variable A for which the derivation
is possible is called nullable.
A grammar may generate a language not containing λ, yet have some λproductions or nullable variables. In such cases, the λ-productions can be
removed.
Example 6.4
Consider the grammar
with start variable S. This grammar generates the λ-free language {a n b n : n ≥ 1}.
The λ-production S 1 → λ can be removed after adding new productions obtained
by substituting λ for S 1 where it occurs on the right. Doing this we get the
grammar
We can easily show that this new grammar generates the same language as the
original one.
In more general situations, substitutions for λ-productions can be made in a