I am having a hard time proving the following with pumping lemma: Is $L_2 = \{a^n \mid \text{$n$ is a product of one or more primes}\}$ regular?

Here's what I have so far:

  • Suppose $L$ is regular, and let $m$ be the constant pumping lemma.

  • Let then $w = a^m$ where $m$ is a product of at least one prime number, therefore $w$ is in the language $L_2$ and $|w| \geq m$.

  • Then $w = xyz$, where $|xy| \leq m$ and $|y| \geq 1$.

  • Then $y = a^j$ where $j \geq 1$.

This is where I'm not sure what to do: Pumping down we get $w_2 = a^{m-j}$

I don't know where to keep going from here since I don't even know if pumping down is the right thing to do.

  • 4
    $\begingroup$ Can you describe some words which are not in L2? $\endgroup$ Oct 14 '19 at 13:17
  • $\begingroup$ I suppose $a$ (i.e., $n=1$) would be one such, since nowadays most people would call 1 a unit, not a prime. $\endgroup$ Oct 14 '19 at 23:41

According to the Fundamental Theorem of Arithmetic, any integer $>1$ can be written as a product of one or more primes (in a unique way). So, it seems that your language can be simplified as $\{a^n\mid n\geq 2\}$.


As all words of length $>1$ and only consisting of a's should be contained in L2, there is a simple finite automaton that recognizes it. So your attempt at using the pumping lemma is futile, as the pumping lemma only helps you prove that a language is irregular if it is, and doesn't tell you anything about languages that are regular.

Maybe I'm also understanding your description of L2 wrong, in that case please add a comment or edit your question.


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.