[Overview] [Previous] [Next]

Pumping Lemma Example 3

Prove that L = {an: n is a prime number} is not regular.

  1. We don't know m, but assume there is one.

  2. Choose a string w = an where n is a prime number and |xyz| = n > m+1. (This can always be done because there is no largest prime number.) Any prefix of w consists entirely of a's.

  3. We don't know the decomposition of w into xyz, but since |xy| <= m, it follows that |z| > 1. As usual, |y| > 0,

  4. Since |z| > 1, |xz| > 1. Choose i = |xz|. Then |xyiz| = |xz| + |y||xz| = (1 + |y|)|xz|. Since (1 + |y|) and |xz| are each greater than 1, the product must be a composite number. Thus |xyiz| is a composite number.
Q.E.D.


Copyright 1996 by David Matuszek
Last modified Feb 20, 1996