1
$\begingroup$

I have some difficulties proving that the language of unary primes ($L=\{1^p\mid p\text{ is prime}\}$) is not regular using the pumping lemma. Any suggestions?

$\endgroup$
3
$\begingroup$

This is one of the more difficult common applications of the pumping lemma, so I'll give you an outline to get you started.

Suppose $L$ is regular and let $k$ be the pumping length. Let $p$ be a big enough prime* so $1^p\in L$, and write $a=1^r1^s1^t$, with $r+s\leq k$ and $s\geq 1$, so $t=p-r-s$. You need to find some $n$ such that $1^r(1^s)^n1^t\notin L$, i.e., such that $r+ns+t$ is not prime, which you can show by writing it as a product of two factors, both strictly bigger than $1$.

* You'll certainly need $p>k$ to apply the pumping lemma, but you might need it to be bigger still, to guarantee that the factors are bigger than $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.