Question

John Doe claims that the language L, of all strings over the alphabet Σ = { a, b } that contain an even number of occurrences of the letter ‘a’, is not a regular language. He offers the following “pumping lemma proof”. Explain what is wrong with the “proof” given below.

“Pumping Lemma Proof”

We assume that L is regular.

Then, according to the pumping lemma, every long string in L (of length m or more) must be “pumpable”.

We choose the specific string w = a^2m .   Clearly w is in L, and | w | >= m, so this w must be “pumpable”.

That means that the string w consist of 3 substrings, x, y, and z. In other words w = xyz. We choose y = a.

Then if we “pump up” to produce the string xy²z , this string should also be in the language L, according to the Pumping Lemma.

But xy²z = a^2m+1 ,    and clearly xy²z is NOT in L, since this new string has an odd number of a’s.

Therefore our original assumption that L is regular was incorrect.      Q.E.D.

Answer 1