so that for it to accept a n b 2n we must further have
for some q j ∈ F. But then, by construction
so that will accept a n b n c n . It remains to be shown that no strings other than
those in are accepted by ; this is considered in several exercises at the end
of this section. The conclusion is that = L ( ), so that is context-free. But
we will show in the next chapter (Example 8.1) that is not context-free.
Therefore, our assumption that L is a deterministic context-free language must
be false.
EXERCISES
1. Show that L = {a n b 2n : n ≥ 0} is a deterministic context-free language.
2. Show that L = {a n b m : m ≥ n + 2} is deterministic.
3. Is the language L = {a n b n : n ≥ 1} ∪ {b} deterministic?
4. Is the language L = {a n b n : n ≥ 1} ∪ {a} deterministic?
5. Show that the pushdown automaton in Example 7.4 is not deterministic, but
that the language in the example is nevertheless deterministic.
6. For the language L in Exercise 1, show that L* is a deterministic context-free
language.
7. Give reasons why one might conjecture that the following language is not
deterministic.
L = { a n b m c k : n = m or m = k}.