8. Is the language L = {a n b m : n = m or n = m + 2} deterministic?
9. Is the language {wcw R : w ∈{a, b}*} deterministic?
10. While the language in Exercise 9 is deterministic, the closely related
language L = {ww R : w ∈{a, b}*} is known to be nondeterministic. Give
arguments that make this statement plausible.
11. Show that L = {w ∈ {a, b}* : n a (w) ≠ n b (w)} is a deterministic context-free
language.
12. Show that in Example 7.11 does not accept a n b n c k for k ≠ n.
13. Show that in Example 7.11 does not accept any string not in L (a*b*c*).
14. Show that in Example 7.11 does not accept a n b 2n c k with k > 0. Show also
that it does not accept a n b m c k unless m = n or m = 2n.
15. Show that every regular language is a deterministic context-free language.
16. Show that if L 1 is deterministic context-free and L 2 is regular, then the
language L 1 ∪ L 2 is deterministic context-free.
17. Show that under the conditions of Exercise 16, L 1 ∩ L 2 is a deterministic
context-free language.
18. Give an example of a deterministic context-free language whose reverse is
not deterministic.
7.4 Grammars for Deterministic Context-Free
Languages*
The importance of deterministic context-free languages lies in the fact that they
can be parsed efficiently. We can see this intuitively by viewing the pushdown
automaton as a parsing device. Since there is no backtracking involved, we can
easily write a computer program for it, and we may expect that it will work
efficiently. Since there may be λ-transitions involved, we cannot immediately
claim that this will yield a linear-time parser, but it puts us on the right track
nevertheless. To pursue this, let us see what grammars might be suitable for the
description of deterministic context-free languages. Here we enter a topic
9. Is the language {wcw R : w ∈{a, b}*} deterministic?
10. While the language in Exercise 9 is deterministic, the closely related
language L = {ww R : w ∈{a, b}*} is known to be nondeterministic. Give
arguments that make this statement plausible.
11. Show that L = {w ∈ {a, b}* : n a (w) ≠ n b (w)} is a deterministic context-free
language.
12. Show that in Example 7.11 does not accept a n b n c k for k ≠ n.
13. Show that in Example 7.11 does not accept any string not in L (a*b*c*).
14. Show that in Example 7.11 does not accept a n b 2n c k with k > 0. Show also
that it does not accept a n b m c k unless m = n or m = 2n.
15. Show that every regular language is a deterministic context-free language.
16. Show that if L 1 is deterministic context-free and L 2 is regular, then the
language L 1 ∪ L 2 is deterministic context-free.
17. Show that under the conditions of Exercise 16, L 1 ∩ L 2 is a deterministic
context-free language.
18. Give an example of a deterministic context-free language whose reverse is
not deterministic.
7.4 Grammars for Deterministic Context-Free
Languages*
The importance of deterministic context-free languages lies in the fact that they
can be parsed efficiently. We can see this intuitively by viewing the pushdown
automaton as a parsing device. Since there is no backtracking involved, we can
easily write a computer program for it, and we may expect that it will work
efficiently. Since there may be λ-transitions involved, we cannot immediately
claim that this will yield a linear-time parser, but it puts us on the right track
nevertheless. To pursue this, let us see what grammars might be suitable for the
description of deterministic context-free languages. Here we enter a topic