18. Apply the pigeonhole argument directly to the language in Example 4.8.
19. Are the following languages regular?
(a)
* (b)
20. Is the following language regular?
21. Let P be an infinite but countable set, and associate with each p ∈ P a
language L p . The smallest set containing every L p is the union over the
infinite set P; it will be denoted by U p ∈ p L p . Show by example that the family
of regular languages is not closed under infinite union.
22. Consider the argument in Section 3.2 that the language associated with any
generalized transition graph is regular. The language associated with such a
graph is
where P is the set of all walks through the graph and r p is the expression
associated with a walk p. The set of walks is generally infinite, so that in
light of Exercise 21, it does not immediately follow that L is regular. Show
that in this case, because of the special nature of P, the infinite union is
regular.
* 23.Is the family of regular languages closed under infinite intersection?
24.Suppose that we know that L 1 ∪ L 2 and L 1 are regular. Can we conclude
from this that L 2 is regular?
25. In the chain code language in Exercise 24, Section 3.1, let L be the set of all
w ∈ u,r,l,d}* that describe rectangles. Show that L is not a regular language.
26. Let
.
(a) Can you use the pumping lemma to show that L is regular?
(b) Can you use the pumping lemma to show that L is not regular? Explain
19. Are the following languages regular?
(a)
* (b)
20. Is the following language regular?
21. Let P be an infinite but countable set, and associate with each p ∈ P a
language L p . The smallest set containing every L p is the union over the
infinite set P; it will be denoted by U p ∈ p L p . Show by example that the family
of regular languages is not closed under infinite union.
22. Consider the argument in Section 3.2 that the language associated with any
generalized transition graph is regular. The language associated with such a
graph is
where P is the set of all walks through the graph and r p is the expression
associated with a walk p. The set of walks is generally infinite, so that in
light of Exercise 21, it does not immediately follow that L is regular. Show
that in this case, because of the special nature of P, the infinite union is
regular.
* 23.Is the family of regular languages closed under infinite intersection?
24.Suppose that we know that L 1 ∪ L 2 and L 1 are regular. Can we conclude
from this that L 2 is regular?
25. In the chain code language in Exercise 24, Section 3.1, let L be the set of all
w ∈ u,r,l,d}* that describe rectangles. Show that L is not a regular language.
26. Let
.
(a) Can you use the pumping lemma to show that L is regular?
(b) Can you use the pumping lemma to show that L is not regular? Explain