is not in L. Therefore, the pumping lemma is violated, and L is not regular.
Example 4.10
The language
is not regular.
Given m, we pick as our string
which is in L. Because of the constraint |xy| ≤ m, both x and y must be in the part
of the string made up of ab’s. The choice of x does not affect the argument, so let
us see what can be done with y. If our opponent picks y = a, we choose i = 0 and
get a string not in L ((ab)* a*}. If the opponent picks y = ab, we can choose i = 0
again. Now we get the string (ab) m a m , which is not in L. In the same way, we
can deal with any possible choice by the opponent, thereby proving our claim.
Example 4.11
Show that
L = {a n : n is a perfect square}
is not regular.
Given the opponent's choice of m, we pick
If w = xyz is the decomposition, then clearly
with 1 ≤ k ≤ m. In that case,