How to prove that $L=${$a^p$: p is prime} isn't regular?

Question

I tried using pumping lemma or finding infinite equivalence classes, but I didn't succeed.

It's clear to me that there is no automata that accepts this language, but I just can't formally prove that this language isn't regular.

How can you prove it?

Answer 1

You can in fact use the pumping lemma to prove that the language $L=\{a^p:p \text{ is prime}\}$ is not regular:

As a reminder and clarification of notation: The pumping lemma states that any word $w\in L$ with $|w|>n$ for a specific $n$ can be split into three parts $w=abc$ so that:

1. $|ab|\leq n$
2. $|b|>0$
3. $\forall i\in \mathbb{N}:ab^ic\in L$

Suppose there exists such an $n$ (which must be true if $L$ is regular). Then there is also a partition of any word $z=abc$ with $|z|>n$ which fulfills the above criteria.

It is clear that the word $z_i=ab^ic$ is of length $$|z_i|=|ac|+i|b|$$ and thus $$|z_i|\equiv |ac|\ (\text{mod }|b|)$$ and $$|z_i|\equiv |ac|-i\ (\text{mod }|b|+1)$$. In the case $i=|ac|$, $$|z_i|\equiv 0\ (\text{mod }|b|+1)$$ holds true. In other words, $|z_{|ac|}|$ would be divisible by $|b|+1$.

Obviously, $|z_i|\neq|b|+1$ in the general case, so $z_{|ac|}$ would therefore not be prime and could not possibly be element of $L$. So there has to exist a word $z=abc$ with $|z|>n$ for which $ab^ic$ is not in the language, independently of $n$ or the choice of $a$, $b$ and $c$. Therefore, $L$ can not be regular. $\quad\square$

Answer 2

Assuming your alphabet $\Sigma$ includes $a$ (if $a$ is an arbitrary word in $\Sigma^*$, then the proof is completely analogous to the method here but a bit fiddlier), the pumping lemma implies that for some $n\geq 0$ and $m > 0$, we have $a^{n + tm}\in L$ for all $t > 0$. But this is clearly false; take $t = n$, for example.