I have these two questions regarding the pumping lemma which, I do not quite fully understand. I was hoping someone can guide me through these questions.

$PRIME$ = {$a^i$ where $i$ is a prime number}

$PRIME′$ = {$a^i$ where $i$ is not prime}

A) Prove that PRIME′ is nonregular (we must first prove that PRIME is nonregular first)

B) Show that PRIME′ does satisfy the pumping lemma (that is, it can't be proven nonregular using the pumping lemma)

  • $\begingroup$ What is $\def\P{\mathsf{PRIME}}\P$? The unary language $$ \{0^p : p \in \mathbf N, p \text{ is prime}\}?$$ And what is $\P'$? $\endgroup$ – martini Mar 17 '16 at 15:51
  • $\begingroup$ @martini just made the edits $\endgroup$ – Csci319 Mar 17 '16 at 15:56

Your Answer

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

Browse other questions tagged or ask your own question.