Question

Using the pumping lemma, prove that the language {1^n | n is a prime number} is not regular.

Answer 1

Pumping lemma for regular language states that,

For any regular language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uvⁱw ∈ L

Given language L is { 1^n | n is prime}. Let us take the strings of length >= k. So, let X be string of length k.

X = uvw = 1^k . Let u = 1^k-2, v = 1, w = 1.

This split of x, y, z satisfies first two conditions of lemma,

|uv| = k - 1 which is <= k

|w| = 1 which is >= 1. So if, all the strings satisfies the condition-3 also, then the language becomes regular. Let's check it too,

Let us assume, 1^k is a string in language, which means k is prime.

Let i = 2, in condition-3. So uvⁱw should belong to L if L is regular.

uvⁱw = 1^k-2.1².1 = 1^k+1

If 1^k belongs to L, 1^k+1 should not be belonging to L. As k is prime, it will be of odd length. So k+1 will be of even length which can't be prime, and doesn't belong to language.

According to pumping lemma both the strings should be in the language for language to be regular. As only one of 1^k and 1^k+1 belongs to language, this language cannot be Regular according to pumping lemma.