-1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Is what reasoning incorrect? I can't tell hat you're actually asking. $\endgroup$
    – David Richerby
    Jun 18, 2016 at 21:36
  • 1
    $\begingroup$ You are assuming that $\overline{\mathrm{REG}}$ is closed under concatenation. Do you have a proof of that? $\endgroup$
    – Raphael ♦
    Jun 18, 2016 at 22:00
  • $\begingroup$ @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. $\endgroup$
    – JohnMadon1234567890
    Jun 18, 2016 at 22:09
  • $\begingroup$ @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 $\endgroup$
    – JohnMadon1234567890
    Jun 18, 2016 at 22:17

2 Answers 2

Reset to default
3
$\begingroup$

No, non regular languages are not closed under the concatenation, therefore the premise is wrong. See Proving that non-regular languages are closed under concatenation for a counterexample.

Improve this answer
$\endgroup$
-2
$\begingroup$

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 accepted answer claims wrongly that the concatenation would always have an even number of a's, when obviously the number of a's can be 2 + p for any odd prime p).

David, I'm deeply disappointed with you. The usual method of demonstrating that an argument is wrong is to show that if the argument was right, it would "prove" something wrong. That's what I did. The argument that the poster gave could be used identically to prove something that is obviously incorrect, therefore the argument is wrong.

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – JohnMadon1234567890
    Jun 18, 2016 at 21:31
  • 2
    $\begingroup$ I don't understand. The title of the question says that $m$ is prime; you can't just say, "Oh, solve something else instead." $\endgroup$
    – David Richerby
    Jun 18, 2016 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.