patternMinor
Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma
Viewed 0 times
provingregularitywithoutmidnontextpumpinglemmaprime
Problem
I was wondering whether it is possible to prove $\{a^p \mid p \in \text{Prime} \}$ is a non-regular language without using the pumping lemma. I'm having trouble choosing an alphabet that completes the proof using Myhill-Nerode and figuring out other methods to use generally.
Solution
Let $L=\{a^p \mid p \in \text{Prime} \}$.
Let $m,n\in\Bbb N$, $m
-
$a^ma^{s-n}=a^{s-(n-m)}$. Note that $(3n)! + 2n
So $s-(n-m)$ is not prime, i.e., $a^ma^{s-n}\not\in L$.
The above shows that $a^m$ and $a^n$ represent different Myhill-Nerode equivalence classes. That means each word represents a distinct Myhill-Nerode equivalence class. Since there are infinitely many of them, $L$ cannot be regular.
Let $m,n\in\Bbb N$, $m
-
$a^ma^{s-n}=a^{s-(n-m)}$. Note that $(3n)! + 2n
- Any number between $(3n)!+3n$ and $s$ exclusive is not a prime number.
So $s-(n-m)$ is not prime, i.e., $a^ma^{s-n}\not\in L$.
The above shows that $a^m$ and $a^n$ represent different Myhill-Nerode equivalence classes. That means each word represents a distinct Myhill-Nerode equivalence class. Since there are infinitely many of them, $L$ cannot be regular.
Context
StackExchange Computer Science Q#105444, answer score: 2
Revisions (0)
No revisions yet.