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