This answer is restricted. Please login to view the answer of this question.

Login NowSuppose 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:

a^{p} ∈L and

a^{p} ^{+ k }∈L as well as

a^{p+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:

a^{p + pk }∈L, of course a^{p + pk }= a^{p (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.

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.

Click here to submit your answer.

HAMROCSIT.COM

## Discussion