L = L 1 ∪ L 2
is context-free as well. This will follow from a general theorem to be presented
in the next chapter, but can easily be made plausible at this point. Let G 1 = (V 1 ,
T, S 1 , P 1 ) and G 2 = (V 2 , T, S 2 , P 2 ) be context-free grammars such that L 1 = L
(G 1 ) and L 2 = L (G 2 ). If we assume that V 1 and V 2 are disjoint and that S V 1 ∪
V 2 , then, combining the two, grammar G = (V 1 ∪ V 2 ∪ {S}, T, S, P), where
P = P 1 ∪ P 2 ∪ {S→ S 1 |S 2 },
generates L 1 ∪ L 2 . This should be fairly clear at this point, but the details of the
argument will be deferred until Chapter 8. Accepting this, we see that L is
context-free. But L is not a deterministic context-free language. This seems
reasonable, since the pda has either to match one b or two against each a, and so
has to make an initial choice whether the input is in L 1 or in L 2 . There is no
information available at the beginning of the string by which the choice can be
made deterministically. Of course, this sort of argument is based on a particular
algorithm we have in mind; it may lead us to the correct conjecture, but does not
prove anything. There is always the possibility of a completely different
approach that avoids an initial choice. But it turns out that there is not, and L is
indeed nondeterministic. To see this we first establish the following claim. If L
were a deterministic context-free language, then
= L ∪ {a n b n c n : n ≥ 0}
would be a context-free language. We show the latter by constructing an npda
for , given a dpda M for L.
The idea behind the construction is to add to the control unit of M a similar
part in which transitions caused by the input symbol b are replaced with similar
ones for input c. This new part of the control unit may be entered after M has
read a n b n . Since the second part responds to cn in the same way as the first part
does to b n , the process that recognizes a n b 2n now also accepts a n b n c n . Figure 7.4
describes the construction graphically; a formal argument follows.
Let M = (Q, Σ, Γ, δ, q 0 , z, F) with
is context-free as well. This will follow from a general theorem to be presented
in the next chapter, but can easily be made plausible at this point. Let G 1 = (V 1 ,
T, S 1 , P 1 ) and G 2 = (V 2 , T, S 2 , P 2 ) be context-free grammars such that L 1 = L
(G 1 ) and L 2 = L (G 2 ). If we assume that V 1 and V 2 are disjoint and that S V 1 ∪
V 2 , then, combining the two, grammar G = (V 1 ∪ V 2 ∪ {S}, T, S, P), where
P = P 1 ∪ P 2 ∪ {S→ S 1 |S 2 },
generates L 1 ∪ L 2 . This should be fairly clear at this point, but the details of the
argument will be deferred until Chapter 8. Accepting this, we see that L is
context-free. But L is not a deterministic context-free language. This seems
reasonable, since the pda has either to match one b or two against each a, and so
has to make an initial choice whether the input is in L 1 or in L 2 . There is no
information available at the beginning of the string by which the choice can be
made deterministically. Of course, this sort of argument is based on a particular
algorithm we have in mind; it may lead us to the correct conjecture, but does not
prove anything. There is always the possibility of a completely different
approach that avoids an initial choice. But it turns out that there is not, and L is
indeed nondeterministic. To see this we first establish the following claim. If L
were a deterministic context-free language, then
= L ∪ {a n b n c n : n ≥ 0}
would be a context-free language. We show the latter by constructing an npda
for , given a dpda M for L.
The idea behind the construction is to add to the control unit of M a similar
part in which transitions caused by the input symbol b are replaced with similar
ones for input c. This new part of the control unit may be entered after M has
read a n b n . Since the second part responds to cn in the same way as the first part
does to b n , the process that recognizes a n b 2n now also accepts a n b n c n . Figure 7.4
describes the construction graphically; a formal argument follows.
Let M = (Q, Σ, Γ, δ, q 0 , z, F) with