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.
6 Answers
Let $L=\{a^p \mid p \in \text{Prime} \}$.
Let $m,n\in\Bbb N$, $m<n$. Let $s$ be the smallest prime number that is bigger than $(3n)! + 3n$.
- $a^na^{s-n}=a^s\in L$.
$a^ma^{s-n}=a^{s-(n-m)}$. Note that $(3n)! + 2n < s - (n-m) < s $.
- Any number between $(3n)! + 2n $ and $(3n)!+ 3n$ inclusive is not a prime number.
- 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.
-
$\begingroup$ To justify this answer, we can say (the proof of) Myhill–Nerode theorem does not use the (proof of) pumping lemma. In fact, it is reasonable to say the finiteness of Myhill-Nerode classes is easier to prove than the pumping lemma. $\endgroup$– John L.Apr 11, 2019 at 14:57
Consider a DFA which has a unary input alphabet. Every state has exactly one successor state. Without restriction of generality, the trace of an input long enough will be $q_0 q_1 \dotsm q_k q_i$, where $q_0, q_1, \dotsc, q_k$ are all distinct states and $i \in \{ 0, \dotsc, k\}$. Hence, $q_i \dotsm q_k q_i$ is a cycle.
If the DFA's language is infinite, there must be an accepting state $q_j$ with $j \in \{ i, \dotsc, k \}$. Note we may assume $j > 1$ since otherwise we immediately obtain $\varepsilon$ or $a$ is in the DFA's language (and neither have prime length). But then $a^{j + m(k - i + 1)}$ is accepted for all $m \in \mathbb{N}_0$. Since $j + j(k - i + 1) > j$ is not prime, the DFA's language contains strings with composite length (unless it is finite).
-
3$\begingroup$ You've basically just proved the pumping lemma for unary alphabets, so I don't think this counts. $\endgroup$ Mar 11, 2019 at 17:17
-
$\begingroup$ Well, not really. It might be in the spirit of the pumping lemma (or, rather, of the pumping lemma's proof), but it does not explicitly rely on it. I'll let the OP decide what counts and what doesn't. $\endgroup$– dkaeaeMar 11, 2019 at 19:44
-
$\begingroup$ Pumping lemma = "Every string that is long enough ends up in a cycle". Myhill-Nerode = "The state that input x ends in is equivalent to the set of suffixes y such that xy is in the language. If the set of suffixes is not finite, the language is not regular". $\endgroup$ Jun 1, 2020 at 11:13
-
$\begingroup$ I'd rewrite the pumping lemma in terms of cycles; I think that is much clearer anyway (and you can reconstruct it easily if you forget the details of the pumping lemma). $\endgroup$ Jun 1, 2020 at 11:14
Parikh's theorem (whose proof in this case is trivial) implies that if your language were regular, then the set of primes would be eventually periodic: there exist $n_0 \geq 0$ and $m \geq 1$ such that for $n \geq n_0$, $n$ is prime iff $n+m$ is prime. In particular, since the set of primes is infinite, it would have positive density. However, it is well-known that the set of primes has vanishing density (this follows from, but is much easier than, the prime number theorem).
-
$\begingroup$ "Parikh's theorem (whose proof in this case is trivial)". However, that trivial proof is sort of including the proof of the pumping lemma (in this case). So it is dubious this answer counts. $\endgroup$– John L.Apr 12, 2019 at 3:51
Another weird way to prove it is using busy beavers and the prime gaps theorem:
suppose that you have a $DFA$ $A$ that accepts the primes $\{ a^p\mid p \text{ prime} \}$
given a state $q$ of $A$, you can build a Turing machine $M_{\langle A,q \rangle}$ that sequentially simulates $A$ starting from state $q$ on inputs $a^1, a^2, a^3, a^4,...$ until $A$ accepts some $a^k$ (or never halt)
let $|M_{\langle q,A \rangle}| = n$ be the size of such Turing machine, and $BB(n)$ the maximum number of steps achievable by a halting Turing machine of size $n$ (uncomputable)
by the prime gaps theorem, there exists a prime $p_i$ such that $p_{i+1} - p_i \gg BB(n)$
$A$ accepts $a^{p_{i+1}}$, so let $q_i$ be the state of $A$ on input $a^{p_{i+1}}$ after $p_{i}$ steps (i.e. it has scanned the first part $a^{p_i}...$ and the head is at the beginning of the remaining part of the input $...a^{p_{i+1} - p_{i}}$)
so there exists $M_{\langle A,q_i\rangle}$ of size $n$ that by construction will run for a number of steps greater than $p_{i+1} - p_i \gg BB(n)$ and halt, contradicting the hypothesis that $BB(n)$ is the maximum number of steps achievable by a halting TM of size $n$
This is probably a better and clearer solution using the Myhill-Nerode Theorem. As there are infinite prime numbers, so for the sake of contradiction, let us assume that the language has finite classes. Thus there exist at least two primes $p_1$ and $p_2$ (wlog $p_2 > p_1$) such that $$[a^{p_1}]_{\equiv_L} = [a^{p_2}]_{\equiv_L}$$ Now, using the right congruence rule on these classes and appending the words with $a^{p_2 - p_1}$, we get $$[a^{p_2}]_{\equiv_L} = [a^{2p_2 - p_1}]_{\equiv_L}$$ which implies$$[a^{p_1}]_{\equiv_L} = [a^{2p_2 - p_1}]_{\equiv_L}$$ Continuing this for $p_1 - 2$ times more we get that $$[a^{p_1}]_{\equiv_L} = [a^{p_1p_2 - (p_1 - 1)p_1}]_{\equiv_L}$$ Clearly, $p_1p_2 - (p_1-1)p_1 = p_1(p_2-p_1+1)$ is not a prime number, whereas $p_1$ is a prime. Hence, the two classes above cannot be equivalent which results in a contradiction and completes our proof that the language is not regular.
-
1
Take two inputs x and y, and for each one find the shortest non-empty string $a^k$ such that adding $a^k$ ends up in an accepting state. If for x and y these strings are different, then x and y must reach different states. If there are infinitely many x and y such that these strings are different, then the language cannot be regular.
Let x = $a^p$ for a prime number p, and g(p) be the gap between p and the next larger prime. Same with y = $a^q$. If g(q) ≠ g(p) then x and y must be in different states. There is a theorem about prime numbers that the gaps between primes become arbitrary large, so there is an unlimited number of different states, and the language is not regular.
The same is true for every set of integers where the gaps between consecutive integers become arbitrary large.