5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ You've basically just proved the pumping lemma for unary alphabets, so I don't think this counts. $\endgroup$ – David Richerby Mar 11 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$ – dkaeae Mar 11 at 19:44
1
$\begingroup$

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).

$\endgroup$
  • $\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$ – Apass.Jack Apr 12 at 3:51
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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