Am using the pumping lemma correctly?

Question

I'm trying to prove that the following language is not regular via the Pumping Lemma. But I'm not truly sure if I have done it correctly.

{L = a²ⁿ | n>= 0 }

What I've done so far is the following:

s = a^2p

x = a²ⁱ

y = a^2j

z = a^2p-i-j

thus xy²z = a^2p+j

which means that a^2p+j > a^2p , making the language not regular

Am I doing it correctly? or is there something I have wrong?

Answer 1

Not quite, you draw the correct conclusion, but the reasoning is a bit off. The Pumping lemma states that for every regular language L, there exists an integer p >= 1 where every string s of length greater than or equal to p can be written as s = xyz where the following conditions hold:

1. y is non-empty
2. The length of xy ≤ p
3. xyⁱz is in the language L for all i ≥ 0

Your first step is correct, s = a^2p is indeed longer than p. However, the pumping lemma states that s can be divided as s = xyz satisfying the above conditions. In other words, there exists a division of s as s = xyz, but you don't get to choose what that division is, beyond knowing that it should satisfy the above three properties.

In your case L is the language consisting of just a's where the number of a's is a power of 2. Now taking s = a^2p, we know that the next longest string in L is (a^2p)². From there, if the first two conditions hold, it can be seen that the third condition certainly cannot hold for i = 2, since a^2p < xy²z < (a^2p)². (In plain english, the length of xy²z is between powers of two, so it is not in the language L as it would have been if it were a regular language)