Broken Pumping Lemma Proofs

This page is an attempt to reconstruct some well-meaning but flawed pumping lemma proofs from a problem set I graded in spring 2006.

Problem: Prove using the pumping lemma that the set of palindromes over {0, 1} is not regular.

Broken proof 1

Suppose that the set of palindromes were regular. Let n be the value from the pumping lemma. Consider the string w = 0n110n. w is clearly a palindrome and |w|>= n. By the pumping lemma, there must exist strings x, y, and z satisfying the four constraints of the pumping lemma.

So, pick any x, y, and z such that w = xyz, |xy| <= n, and |y| >= 1. Because |xy| <= n, xy is entirely contained in the 0n at the start of w. So x and y consist entirely of zeros.

Now, consider xz. By the pumping lemma, xz must be in the language. But xz can't be a palindrome. This means that the set of palindromes doesn't satisfy the pumping lemma and, thus, the set of palindromes cannot be regular.

This proof doesn't contain enough detail about why xz isn't a palindrome. It's really just a copy of the template with a string w filled in.

Broken proof 2

Suppose that the set of palindromes were regular. Let n be the value from the pumping lemma. Consider the string w = 00011000. w is clearly a palindrome. By the pumping lemma, there must exist strings x, y, and z satisfying the four constraints of the pumping lemma.

So, pick any x, y, and z such that w = xyz, |xy| <= n, and |y| >= 1. Because |xy| <= n, xy is entirely contained in the 0n at the start of w. So x and y consist entirely of zeros.

Now, consider xz. By the pumping lemma, xz must be in the language. But xz can't be a palindrome. This means that the set of palindromes doesn't satisfy the pumping lemma and, thus, the set of palindromes cannot be regular.

This proof has an even bigger mistake. It's using a fixed string w, whose length doesn't depend on n. There's no way to flesh out the later bits of the proof if you have done this. The string w has to get longer as n gets bigger.

Broken proof 3

Suppose that the set of palindromes were regular. Let n be the value from the pumping lemma. Consider a string w in L, with |w|>= n. By the pumping lemma, there must exist strings x, y, and z satisfying the four constraints of the pumping lemma.

So, pick any x, y, and z such that w = xyz, |xy| <= n, and |y| >= 1. Because |xy| <= n, y is contained in the first n characters of w.

Now, consider xz. By the pumping lemma, xz must be in the language. But xz can't be a palindrome. This means that the set of palindromes doesn't satisfy the pumping lemma and, thus, the set of palindromes cannot be regular.

Wow. This proof never assigned a value to w. There's no way you can write a pumping lemma proof without a specific value for w. In fact, all they did was to copy the pumping lemma proof template without adding specific details for this problem.

Broken proof 4

Suppose that the set of palindromes were regular. Let n be the value from the pumping lemma. Consider the string w = (01)n(10)n. w is clearly a palindrome and |w|>= n. By the pumping lemma, there must exist strings x, y, and z satisfying the four constraints of the pumping lemma.

So, pick any x, y, and z such that w = xyz, |xy| <= n, and |y| >= 1. Because |xy| <= n, xy is entirely contained in the (01)n at the start of w. So y must be (01)i for some integer i >= 1.

Now, consider xz. xz = (01)n-i(10)n. By the pumping lemma, xz is supposed to be in the language. But the number of 01 and 10 pairs don't match (since i >= 1), so xz can't be a palindrome.

This means that the set of palindromes doesn't satisfy the pumping lemma and, thus, the set of palindromes cannot be regular.

Since your adversary gets to pick how w is divided into x, y, and z, y might not actually be a neat set of 01 pairs. y might start with a 1 or end with a 0. The middle bit of this proof would need to patched up. It probably can be, since w is so much longer than n, but it's not going to be easy.

A better way to fix this proof would be to find a better choice for w.

Broken proof 5

Suppose that the set of palindromes were regular. Let n be the value from the pumping lemma. Consider the string w = 0n110n.

w = xyz, |xy| <= n, and |y| >= 1. So y consists entirely of zeros, i.e. y = 0j.

xz = 0i.0k110n = 0i+k110n. Since j>=1, i + k < n. So xz is not a palindrome, because the numbers of zeros on the two ends don't match.

This proof has the right key steps, but not enough "glue" words. Assertions appear without any sense of where they came from. Variables (e.g. x,y,z) appear without proper introduction.

Accurately copying the pumping lemma template would have helped here.

Broken proof 6

Suppose that the set of palindromes were regular. Let n be the value from the pumping lemma. Consider the string w = 0n110n. w is clearly a palindrome and |w|>= n.

Let x, y, and z be strings satisfying the four constraints of the pumping lemma. x = 0i, y = 0j and z = 0k110n, where i + j + k = n.

Now, consider xz. By the pumping lemma, xz must be in the language. But xz = 0i.0k110n. This is just 0i+k110n. Since |y| >= 1, we know that j>=1. So i + k < n. This means that xz is not a palindrome, because the numbers of zeros on the two ends don't match.

This means that the set of palindromes doesn't satisfy the pumping lemma and, thus, the set of palindromes cannot be regular.

This proof is mostly correct. However, it would lose a small number of points because the second paragraph never explained why x, y, and z must have that form. It's important to mention explicitly that |xy| <= n and that, therefore, y consists entirely of zeros.

Broken proof 7

Suppose that the set of palindromes were regular. Let n be the value from the pumping lemma. Consider the string w = 0n110n. w is clearly a palindrome and |w|>= n. By the pumping lemma, there must exist strings x, y, and z satisfying the four constraints of the pumping lemma.

So, pick any x, y, and z such that w = xyz, |xy| <= n, and |y| >= 1. Because |xy| <= n, xy is entirely contained in the 0n at the start of w. So x and y consist entirely of zeros, i.e. x = 0i and y = 0j. Then z must look like 0k110n, where i + j + k = n.

Now, consider xz. By the pumping lemma, xz must be in the language. But xz = 0i.0k110n. This is just 0i+k110n. This means that xz is not a palindrome, because the numbers of zeros on the two ends don't match.

This means that the set of palindromes doesn't satisfy the pumping lemma and, thus, the set of palindromes cannot be regular.

Another almost correct proof. The minor bug here is not arguing that i + k < n (because |y| >= 1).

Correct solution

Suppose that the set of palindromes were regular. Let n be the value from the pumping lemma. Consider the string w = 0n110n. w is clearly a palindrome and |w|>= n. By the pumping lemma, there must exist strings x, y, and z satisfying the four constraints of the pumping lemma.

So, pick any x, y, and z such that w = xyz, |xy| <= n, and |y| >= 1. Because |xy| <= n, xy is entirely contained in the 0n at the start of w. So x and y consist entirely of zeros, i.e. x = 0i and y = 0j. Then z must look like 0k110n, where i + j + k = n.

Now, consider xz. By the pumping lemma, xz must be in the language. But xz = 0i.0k110n. This is just 0i+k110n. Since |y| >= 1, we know that j>=1. So i + k < n. This means that xz is not a palindrome, because the numbers of zeros on the two ends don't match.

This means that the set of palindromes doesn't satisfy the pumping lemma and, thus, the set of palindromes cannot be regular.