What is the difference between L(G) and L( )?
14. Suppose that G is a context-free grammar for which λ ∈ L (G). Show that if
we apply the construction in Theorem 6.3, we obtain a new grammar such
that L( ) = L (G) – {λ}.
15. Give an example of a situation in which the removal of λ-productions
introduces previously nonexistent unit-productions.
16. Let G be a grammar without λ-productions, but possibly with some unitproductions. Show that the construction of Theorem 6.4 does not then
introduce any λ-productions.
17. Show that if a grammar has no λ-productions and no unit-productions, then
the removal of useless productions by the construction of Theorem 6.2 does
not introduce any such productions.
18. Justify the claim made in the proof of Theorem 6.1 that the variable B can
be replaced as soon as it appears.
19. Suppose that a context-free grammar G = (V, T, S, P) has a production of the
form
A → xy,
where
. Prove that if this rule is replaced by
where B ∉ V, then the resulting grammar is equivalent to the original one.
20. Consider the procedure suggested in Theorem 6.2 for the removal of useless
productions. Reverse the order of the two parts, first eliminating variables
that cannot be reached from S, then removing those that do not yield a
terminal string. Does the new procedure still work correctly? If so, prove it.
If not, give a counterexample.
21. It is possible to define the term simplification precisely by introducing the
concept of complexity of a grammar. This can be done in many ways; one of
them is through the length of all the strings giving the production rules. For
example, we might use
14. Suppose that G is a context-free grammar for which λ ∈ L (G). Show that if
we apply the construction in Theorem 6.3, we obtain a new grammar such
that L( ) = L (G) – {λ}.
15. Give an example of a situation in which the removal of λ-productions
introduces previously nonexistent unit-productions.
16. Let G be a grammar without λ-productions, but possibly with some unitproductions. Show that the construction of Theorem 6.4 does not then
introduce any λ-productions.
17. Show that if a grammar has no λ-productions and no unit-productions, then
the removal of useless productions by the construction of Theorem 6.2 does
not introduce any such productions.
18. Justify the claim made in the proof of Theorem 6.1 that the variable B can
be replaced as soon as it appears.
19. Suppose that a context-free grammar G = (V, T, S, P) has a production of the
form
A → xy,
where
. Prove that if this rule is replaced by
where B ∉ V, then the resulting grammar is equivalent to the original one.
20. Consider the procedure suggested in Theorem 6.2 for the removal of useless
productions. Reverse the order of the two parts, first eliminating variables
that cannot be reached from S, then removing those that do not yield a
terminal string. Does the new procedure still work correctly? If so, prove it.
If not, give a counterexample.
21. It is possible to define the term simplification precisely by introducing the
concept of complexity of a grammar. This can be done in many ways; one of
them is through the length of all the strings giving the production rules. For
example, we might use