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

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.

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

## 2 Answers

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.