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.

  • $\begingroup$ 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? $\endgroup$ – TheSalamander Oct 13 '15 at 7:25
  • 1
    $\begingroup$ 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\}$ $\endgroup$ – martini Oct 13 '15 at 7:26
  • $\begingroup$ Ah yes, forgot about that! Thanks so much! $\endgroup$ – TheSalamander Oct 13 '15 at 7:31

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.