World's most popular travel blog for travel bloggers.

[Solved]: Concatenation of $a^p$ and $a^m$ where $p$ and $m$ are primes, is irregular?

, , No Comments
Problem Detail: 

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?

Asked By : JohnMadon1234567890

Answered By : JohnMadon1234567890

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59800

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback