# Is C* regular if C is a language with strings of prime length?

Let $C = \{a^p \ | \ p \ \text{is prime}\}$ be a language. I was able to show that $C$ is not regular using the pumping lemma.

However, I am having some trouble showing that $C^*$ is regular. Intuitively I believe it should be regular but I do not know how to construct a proof.

Any thoughts on how to do this one?

Hint: Try to find an explicit expression of $C^*$ in the form $$C^* = \{a^n \mid n \in \text{fill in the right subset A of \mathbf N here}\}$$ By the very definition of the Kleene star, we have $$A = \{n \in \mathbf N \mid n \text{ is a sum of prime numbers}\}$$ I'm sure you can find $A$, just think of $2$ and $3$, more primes are not needed.
• I think I see. $aa,aaa\in C$ so you can keep concatenating $aa$ to these strings to get the form $2+2n, 3+2n$ which covers all even and odd numbers greater than or equal to 2, which covers all $n\geq 2$. Does that sound about right? – TheSalamander Oct 13 '15 at 7:25
• Right ... almost ... you forgot $n=0$, which is by definition part of $C^*$, but otherwise you are right, $C^* = \{a^n \mid n \ne 1\}$ – martini Oct 13 '15 at 7:26