# Determining if (infinite) binary language DFAs contain at least 1 prime?

This problem has been given by Shallit as an open DFA/ complexity theory problem and is currently not even known to be decidable. It seems to be circulating on the internet in a few places (e.g. [1][2]) but not in any papers. Almost nothing seems to be known or published. I am looking for any nontrivial analysis or references.

Given: binary DFA D. Does L(D) contain at least 1 prime?

(Binary means Σ = {0, 1}.) As an example of something nontrivial about it (a subproblem), what can be said of the base-2 DFA language representations, what is their general form? Or, given any d, does there exist a DFA (language) that contains only multiples of d in binary? Are there arithmetic progressions embedded in DFA binary languages? Note there are many number theoretic investigations into primes in arithmetic sequences/ progressions and recent findings/ research, could any be demonstrated to be applicable?

[1] a simple problem whose decidability is not known / cstheory.SE

[2] are there any open problems left about DFAs? / cstheory.SE

• Just a note: the problem is decidable over unary alphabets ($\Sigma = \{1\}$). Indeed, in that case, the regular language forms a semilinear set; so for each one of the arithmetic progressions $\{a + ib \mid i > 0\}$ of the semilinear set (that can be computed efficiently), if $a,b$ are coprimes, then by Dirichlet's theorem, the sequence contains infinite primes.
– Vor
Commented Oct 13, 2015 at 16:40
• fyi/ thx MW for this ref in chat: Minimal Elements for the Prime Numbers/ Bright, Devillers, Shallit
– vzn
Commented Apr 8, 2016 at 16:56

It's a standard intro theory exercise that for any $d\ge 0$ there's a FA that accepts all and only those strings in $\{0, 1\}^*$ that are the binary representations of integer multiples of $d$. Thus, the answer to your second question is "yes".
For your third question, the answer is "no". Consider the regular language denoted by $1(10)^*0$. This language consists of those binary representations of $$\frac{10\cdot 4^n-4}{3}$$ and clearly this sequence is too sparse to contain an arithmetic subsequence of any length greater than 2.
• To hint at how to construct such a DFA for a given $d$: make the initial state the only final state, and count modulo $d$. Commented Oct 10, 2015 at 23:48