Show that L = { an | n is a prime number } is not a regular language.

Question

Bipin Tiwari · Accepted Answer

Suppose n=k; Proof by contradiction: Let us assume L is regular. Clearly L is infinite (there are infinitely many prime numbers). From the pumping lemma, there exists a number n such that any string w of length greater than n has a “repeatable” substring generating more strings in the language L. Let us consider the first prime number p ≥ n. From the pumping lemma the string of length p has a “repeatable” substring. We will assume that this substring is of length k ≥ 1. Hence: ap ∈L         and ap + k ∈L   as well as ap+2k  ∈ L, etc. It should be relatively clear that p + k, p + 2k, etc., cannot all be prime but let us add k p times, then we must have: ap + pk ∈L, of course ap + pk = ap (k + 1) so this would imply that (k + 1)p is prime, which it is not since it is divisible by both p and k + 1. Hence L is not regular.

Show that L = { aⁿ | n is a prime number } is not a regular language.

Leave your Answer:

Hits Counter

Question

Show that L = { an | n is a prime number } is not a regular language.

Leave your Answer:

Show that L = { aⁿ | n is a prime number } is not a regular language.