Is L2 = {a^n| n is a product of one or more primes} regular?

Question

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.

Answer 1

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\}$.

Answer 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.