12. Here you need a little trick. If L contains no even-length strings, then
The left side is regular, so we can use Theorem 4.6.
Section 4.3
2. For the dfa for L to process the middle string v requires a walk in the
transition graph of length |v|. If this is longer than the number of states in the
dfa, there must be a cycle labeled y in this walk. But clearly this cycle can be
repeated as often as desired without changing the acceptability of a string.
4. (a) Given m, pick w = a m b m a 2m . The string y must then be a k and the pumped
strings will be
If we take i ≥ 2, then m + (i − 1) k > m, and then w i is not in L.
(e) It does not seem easy to apply the pumping lemma directly, so we
proceed indirectly. Suppose that L were regular. Then by the closure of
regular languages under complementation, would also be regular.
But
, which, as is easily shown, is not regular.
By contradiction, L is not regular.
5. (a) Take p to be the smallest prime number greater or equal to m and choose
w = a p . Now y is a string of a’s of length k, so that
If we take i − 1 = p, then p + (i − 1) k = p (k + 1) is composite and w p+1 is
not in the language.
14. The proposition is false. As a counterexample, take L 1 = {a n b m : n ≤ m} and
L 2 = {a n b m : n > m}, both of which are nonregular. But L 1 ∪ L 2 = L(a * b * ),
which is regular.
15. (a) The language is regular. This is most easily seen by splitting the problem
into cases such as l = 0, k = 0, n > 5, for which one can easily construct
regular expressions.
The left side is regular, so we can use Theorem 4.6.
Section 4.3
2. For the dfa for L to process the middle string v requires a walk in the
transition graph of length |v|. If this is longer than the number of states in the
dfa, there must be a cycle labeled y in this walk. But clearly this cycle can be
repeated as often as desired without changing the acceptability of a string.
4. (a) Given m, pick w = a m b m a 2m . The string y must then be a k and the pumped
strings will be
If we take i ≥ 2, then m + (i − 1) k > m, and then w i is not in L.
(e) It does not seem easy to apply the pumping lemma directly, so we
proceed indirectly. Suppose that L were regular. Then by the closure of
regular languages under complementation, would also be regular.
But
, which, as is easily shown, is not regular.
By contradiction, L is not regular.
5. (a) Take p to be the smallest prime number greater or equal to m and choose
w = a p . Now y is a string of a’s of length k, so that
If we take i − 1 = p, then p + (i − 1) k = p (k + 1) is composite and w p+1 is
not in the language.
14. The proposition is false. As a counterexample, take L 1 = {a n b m : n ≤ m} and
L 2 = {a n b m : n > m}, both of which are nonregular. But L 1 ∪ L 2 = L(a * b * ),
which is regular.
15. (a) The language is regular. This is most easily seen by splitting the problem
into cases such as l = 0, k = 0, n > 5, for which one can easily construct
regular expressions.