$Prove that language L = {a^p ; p is prime} isn't regular using Myhill-Nerode theorem.$

Question

$Prove that language L = {a^p ; p is prime} isn't regular using Myhill-Nerode theorem.$

Prove that language L = {a^p ; p is prime} isn't regular using Myhill-Nerode theorem.

Algebra

Iamjustjerry

Report

Daniel90

0

Low bounty!

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to 50% commission on every question your affiliated users ask or answer.

Answer 1

Answers can be viewed only if

The questioner was satisfied and accepted the answer, or
The answer was disputed, but the judge evaluated it as 100% correct.

View the answer

Let's show that, given two primes $p, q$, we have $a^p \not \sim_L a^q$, that is, they lie in two different equivalence classes.

Assume by contradiction that $a^p \sim_L a^q$, and wlog $q > p$. Since $a^p a^{q-p} = a^q \in L$, then $a^q a^{q-p} = a^{2q-p} \in L$ as well, otherwise $a^{q-p}$ would be a distinguishing relation for $a^p$ and $a^q$. Iterating the argument, since $a^p a^{2q-2p} = a^{2q-p} \in L$, then $a^q a^{2q-2p} = a^{3q-2p} \in L$, and by induction $a^{p+i(q-p)} \in L$ for every $i$.

But for $i=p$ we have that $p + p(q-p)$ is a multiple of $p$, so it cannot be a prime, a contradiction.

Alessandro Iraci

Iamjustjerry

0

Thank you. Also what is the "wlog" in the second sentence?
Alessandro Iraci

0

Without loss of generality. It means that I can take q>p or p>q and it doesn't matter.

$Prove that language L = {a^p ; p is prime} isn't regular using Myhill-Nerode theorem.$

Answer

Related Questions

Search