# Concatenation of $a^p$ and $a^m$ where $p$ and $m$ are primes, is irregular?

I believe that the concatenation $a^pa^m$ where $p$ and $m$ are primes is not regular, since I can show that $a^p$ is not regular using the pumping lemma, therefore there is no NFA for the 1st part, therefore the concatenation cannot be regular (I.e. there is no NFA to do the lambda transition)

Is the above reasoning correct?

• Is what reasoning incorrect? I can't tell hat you're actually asking. – David Richerby Jun 18 '16 at 21:36
• You are assuming that $\overline{\mathrm{REG}}$ is closed under concatenation. Do you have a proof of that? – Raphael Jun 18 '16 at 22:00
• @Raphael Yup, draw the NFA of $L_1$ and connected it with a lambda transition to the NFA of $L_2$, which makes it closed under concatenation since you can show that a language is regular just by showing that you can make an NFA. – JohnMadon1234567890 Jun 18 '16 at 22:09
• @Raphael Nvm I understand what you meant; no, non regular languages are not closed under the concatenation, therefore no I don't have a proof for that; I guess your question made me answer my question – JohnMadon1234567890 Jun 18 '16 at 22:17

Contrary to the accepted answer, the language is irregular, but the reasoning is wrong. Instead of requiring m to be a prime, require m to be just any integer ≥ 0. Your argument would stay intact, but the language is actually the regular language $a^n$ for n ≥ 2.
The argument given only used that $a^p$ where p is prime was irregular. Nothing about the second language $a^m$, m prime, was used at all. Therefore for the argument to be correct, the concatenation of $a^p$, p prime, with any other language would have to be irregular. Which is incorrect.
• Would that reasoning hold for this case though? I understand that the closure is only for 2 regular languages, and the rest of the cases are not defined. Also, the language is not the regular language $a^n$ for n>=2, since there is not way to do $a^2$, $a^3$, $a^5$ or $a^{16}$, etc, for example. Correct me if I am wrong please – JohnMadon1234567890 Jun 18 '16 at 21:31
• I don't understand. The title of the question says that $m$ is prime; you can't just say, "Oh, solve something else instead." – David Richerby Jun 18 '16 at 21:35