# Prove that the language of non-prime numbers written in unary is not regular

Im trying to prove that the following language is not regular. $$\text{Notprime} = \{a^n \text{where $$n$$ isn't prime}\} = \{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\}$$

Heres what I have:

"If Notprime were regular, then its complement would be regular also. However, the complement of Notprime is the language Prime, hence Notprime is non-regular."

Is this the right way of proving it? Any help is appreciated!

• Yes, if you know that $prime$ is not-regular, you can use the closure properties of regular languages to show that $Notprime$ cannot be regular. Also, see this question. – Ran G. Oct 9 '12 at 22:33
For an with a single letter, there is a general form for all regular languages: they are the languages that, for sufficiently long words, consist of the union of several arithmetic progressions with the same coefficient: $\{a^{ak+b} \mid k\in\mathbb{N}, b \in B\}$ for some fixed $a$ and some finite set $b$. See What are the possible sets of word lengths in a regular language? for a more precise description and a proof. The set of primes, or the set of non-primes, does not have this structure since there are growingly large gaps between primes.