Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.

Question

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.

It seems to use one Lemma: Pumping Lemma.

Answer 1

By Pumping lemma there exists $m \geq 1$ such that every word $1^p \in L$ with $p \geq m$ can be written as $1^p = xyz$ for some $x, y, z \in \{ 1\}^*$, $|y| \geq 1$ so that $xy^kz \in L$ for all $k$. Let $p$ be a prime larger that $m$ and let $k = p + 1$ to get a contradiction.

Answer 2

In addition:

Instead of Pumping lemma one can use the following fact: $L$ is regular iff it is an union of $\lambda$-classes for some left congruence $\lambda$ on the free monoid $A^*$ such that $|A^*/\lambda|<\infty$. Here $A=\{a\}$ (in your notation $a=1$) is commutative, so $\lambda$ is two-sided. The structure of the factor-monoid $A^*/\lambda =\langle {\bar a}\rangle$ is well-known -- it is defined by a relation ${\bar a}^{n+r}={\bar a^n}$. Therefore every $\lambda$-class is either one-element $\{a^k\}$ for $k< n$ or has the form $\{a^k,a^{k+r},a^{k+2r},\ldots\}$ for $k\ge n$. Since $L$ contains an infinite $\lambda$-class, we get a contradiction.