(b) This language is not regular. If we choose w = aaaaaab m a m , our
opponent has several choices. If y consists of only a’s, we use i = 0 to
violate the condition n > 5. If the opponent chooses y as consisting of
b’s, we can then violate the condition k ≤ l.
17. L is regular. We see this from
and the known closures for
regular languages.
19. (a) The language is regular, since any string that has two consecutive
symbols that are the same is in the language. A regular expression for L is (a
+ b)(a + b) * (aa + bb)(a + b)(a + b) * .
(b) The language is not regular. Take w = (ab) m aa (ba) m . The adversary now
has several choices, such as y = (ab) k or y = (ab) k a. In the first case
Since the only possible identification is ww R = (ab) 1 aa(ba) 1 , the prefix u is
shorter than the suffix v, and w 0 is not in L. With the second choice, the
length of w 0 is odd, so it cannot be in L either.
21. Take L i = a i b i , i = 0,1,…. For each i, L i is finite and therefore regular, but the
union of all the languages is the nonregular language L = {a n b n : n ≥ 0}.
25. A rectangle is described by u n r m d n l m . This is not regular, by a
straightforward application of the pumping lemma.
Chapter 5
Section 5.1
4. It is quite obvious that any string generated by this grammar has the same
number of a’s as b’s. To show that the prefix condition n a (v) ≥ n b (v) holds,
we carry out an induction on the length of the derivation. Suppose that for
every sentential form derived from S in n steps this condition holds. To get a
sentential form in n + 1 steps, we can apply S → λ or S → SS. Since neither
of these changes the number of a’s and b’s or the location of those already
there, the prefix condition continues to hold. Alternatively, we apply S →
aSb. This adds an extra a and an extra b, but since the added a is to the left of
opponent has several choices. If y consists of only a’s, we use i = 0 to
violate the condition n > 5. If the opponent chooses y as consisting of
b’s, we can then violate the condition k ≤ l.
17. L is regular. We see this from
and the known closures for
regular languages.
19. (a) The language is regular, since any string that has two consecutive
symbols that are the same is in the language. A regular expression for L is (a
+ b)(a + b) * (aa + bb)(a + b)(a + b) * .
(b) The language is not regular. Take w = (ab) m aa (ba) m . The adversary now
has several choices, such as y = (ab) k or y = (ab) k a. In the first case
Since the only possible identification is ww R = (ab) 1 aa(ba) 1 , the prefix u is
shorter than the suffix v, and w 0 is not in L. With the second choice, the
length of w 0 is odd, so it cannot be in L either.
21. Take L i = a i b i , i = 0,1,…. For each i, L i is finite and therefore regular, but the
union of all the languages is the nonregular language L = {a n b n : n ≥ 0}.
25. A rectangle is described by u n r m d n l m . This is not regular, by a
straightforward application of the pumping lemma.
Chapter 5
Section 5.1
4. It is quite obvious that any string generated by this grammar has the same
number of a’s as b’s. To show that the prefix condition n a (v) ≥ n b (v) holds,
we carry out an induction on the length of the derivation. Suppose that for
every sentential form derived from S in n steps this condition holds. To get a
sentential form in n + 1 steps, we can apply S → λ or S → SS. Since neither
of these changes the number of a’s and b’s or the location of those already
there, the prefix condition continues to hold. Alternatively, we apply S →
aSb. This adds an extra a and an extra b, but since the added a is to the left of