<p>Here's a very simple decision problem about DFA's.  Given a DFA M, does M accept the base-2 representation of at least one prime number? </p>

<p>Currently, we don't even know if this problem is recursively solvable. </p>

<p>If it is recursively solvable, and we had an algorithm for it, we could resolve the longstanding open problem about whether there are any Fermat primes (primes of the form $2^{2^n} + 1$) larger than the largest known one, 65537.  (Because any prime with base-2 representation of the form $1 0^+ 1$ must be a Fermat prime.)</p>

CC BY-SA 3.0
2014-05-14T16:31:46.600Z
there are various other conjectures in number theory that relate to periods eg [Erdos Discrepancy problem](http://en.wikipedia.org/wiki/%C2%B11-sequence#Erd.C5.91s_discrepancy_problem) & tieing some into DFA formulations seems possible in other cases too, a possible research program for someone...
vzn
CC BY-SA 3.0
2017-05-03T20:56:14.853Z
Do I understand it correctly that if we had an algorithm for this problem, this would also solve Sierpinski's problem and the Riesel problem? (https://en.wikipedia.org/wiki/Sierpinski_number, https://en.wikipedia.org/wiki/Riesel_number)
sdcvvc
CC BY-SA 3.0
2017-05-04T17:01:30.453Z
Yes, sdcvvc, that is the case.
Jeffrey Shallit
CC BY-SA 3.0
2014-05-11T12:44:41.440Z
2014-05-11T13:10:46.797Z
2014-05-11T13:10:46.797Z
Jeffrey Shallit
<p>The Černý conjecture is still open and important. It is about DFAs that have a <a href="https://en.wikipedia.org/wiki/Synchronizing_word">synchronizing word</a> (a word with the property that two copies of the automaton started in different states always end up in the same state as each other after both processing the word), and asks whether (for $n$-state automata) the length of the shortest such word is always at most $(n-1)^2$. The best proven bounds are of the form $O(n^3)$.</p>

CC BY-SA 3.0
2014-05-11T04:46:47.233Z
Sorry, Abuzer Yakaryilmaz, didn't notice your comment before posting this as an answer. But I do believe it deserves to be an answer and not just a comment...
David Eppstein
CC BY-SA 3.0
2014-05-11T06:04:27.693Z
No problem :) I think the second open problem that I linked also looks quite interesting.
Abuzer Yakaryilmaz
CC BY-SA 3.0
2014-05-16T13:13:45.863Z
I know this is a famous question, but is there a quick explanation why it is an important one? What would we learn if the bound really is $(n-1)^2$ rather than $n^3/6$?
Sasho Nikolov
CC BY-SA 3.0
2017-03-20T14:10:34.570Z
@SashoNikolov It can be of practical interest to be able to reset a system to a known state without having to observe it (a satellite for instance), using the least number of actions.
Denis
CC BY-SA 3.0
2017-11-17T01:34:48.410Z
Yes, I first learned of this problem through the work of Natarajan on designing components of assembly lines that mechanically force the parts on them to be in certain geometric orientations. Shorter reset sequences (in an automaton representing potential reorientation steps) = shorter assembly lines.
David Eppstein
CC BY-SA 3.0
2014-05-11T04:02:56.657Z
2014-05-11T04:02:56.657Z
David Eppstein
<p>I want to point out the another research problem, which concerns the interplay of very basic concepts about DFAs. </p>

<p>It is well known that any n-state NFA can be converted into an equivalent DFA having at most $2^n$ states. This is best possible in the worst case, in the sense that there are regular languages of nondeterministic state complexity n (i.e., the number of states in a minimal NFA), but of deterministic state complexity $2^n$. There are also examples of language families, where nondeterminism can save a quadratic factor, and cases where nondeterminism does not help to save any states at all. Thus a natural question is the following:</p>

<p><strong>Magic number problem</strong></p>

<p>Is there, for each $\alpha$ between $n$ and $2^n$, a regular language $L_n$ such that the gap between nondeterministic state complexity and deterministic state complexity is exactly $\alpha$? </p>

<p>If we completely understand the powerset construction and the Myhill-Nerode relation from a mathematical perspective, then I'll expect that one is able to construct such languages for each $\alpha$, or alternatively to specify the values of $\alpha$ for which this is impossible (if such values exist, these are referred to as "magic numbers").</p>

<p>It is known that there are magic numbers for input alphabet size $1$, and, since 2009, that there are no magic numbers if the alphabet size is at least $3$. But if I am not mistaken, the case of binary alphabets is still open. </p>

<p>Galina Jirásková. Magic numbers and ternary alphabet. In: 13th International Conference on Developments in Language Theory (DLT 2009), volume 5583 of Lecture Notes in Computer Science, pages 300–311.</p>

CC BY-SA 3.0
2014-05-11T22:59:06.590Z
It's a great problem!   But whoever invented the term "magic number" should be shot.
Jeffrey Shallit
CC BY-SA 3.0
2014-05-11T20:07:20.087Z
2014-05-11T20:07:20.087Z
Hermann Gruber
<p><strong>Title:</strong> Intersection non-emptiness for two DFA's</p>

<p><strong>Description:</strong> Given two DFA's $D_1$ and $D_2$, does there exist a string $x$ such that $D_1$ and $D_2$ both accept $x$?</p>

<p><strong>Open Problem:</strong> Can we solve intersection non-emptiness for two DFA's in $o(n^2)$ time?</p>

<p>If we could solve this problem in $O(n^{\delta})$ time where $\delta$ &lt; 2, then the strong exponential time hypothesis would be refuted.</p>

<p><strong>Explanation:</strong> <a href="https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time">Deciding emptiness of intersection of regular languages in subquadratic time</a></p>

<p>You might find this helpful: <a href="http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/" rel="noreferrer">http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/</a></p>

<p>Have a great day!  :)</p>

CC BY-SA 3.0
2014-05-15T15:16:22.997Z
hi MW glad you noticed this question. recently cited you on this other question re [separating P/L](http://cstheory.stackexchange.com/a/22466/7884). as you have recently proven, the above question (upper bounds on complexity of solving intersection non-emptiness of multiple DFAs) is closely related to (the major open problem of) separating P/NL.
vzn
CC BY-SA 3.0
2014-05-15T19:13:50.983Z
Thank you very much!  Who are you vzn?  I went to your blog and looked around, but couldn't figure it out.
Michael Wehar
CC BY-SA 3.0
2015-11-05T04:43:03.057Z
**Note:** the smallest string accepted by $D_1$ and $D_2$ has length $\Omega(n^2)$ in the worst case.
Michael Wehar
CC BY-SA 3.0
2014-05-15T07:25:16.817Z
2015-01-20T01:12:49.673Z
2017-04-13T12:32:30.623Z
Michael Wehar
<p>Minimal cover automata is one of a related stuff. Given a finite language $L$, we can obtain a minimal DFA for $L$. But if we relax requirements of DFA we can find smaller ones. We know that longest word in a finite language $L$ has length $l$. Define DFCA as a DFA which accepts only words in $L$ or possibly words which are longer than $l$. Then this DFCA can has smaller size than DFA for $L$. In practice checking a length of a word is not matter. If we have a smaller DFCA which accepts original ones we simply can reject words with length larger than $l$. There has been some research on this class (introduced at 2001), and e.g there is an $O(n^2)$ <a href="http://www.dcc.fc.up.pt/~rvr/resources/Aulas-Babel/MAPI-AA/2002_Campeanu.pdf" rel="nofollow">algorithm</a> for finding minimal DFCA. An optimal running time algorithm is not known yet. Also there are other aspects of DFA that we can consider them about DFCA.</p>

CC BY-SA 3.0
2014-05-11T10:26:07.563Z
2014-05-13T21:23:42.527Z
2014-05-13T21:23:42.527Z
Saeed
<p>Here's an open problem relating DFA and machine learning theory: are uniformly random (random transitions and accept/reject behavior) DFA learnable in the PAC model?</p>

<p>Note: we think arbitrary DFA are not learnable b/c of <a href="http://robotics.upenn.edu/~mkearns/papers/crypto.pdf">cryptographic hardness</a> results.  For random DFA, we only have <a href="http://www.levreyzin.com/papers/AngluinEKR10.pdf">SQ lower bounds</a>, which are not as strong.</p>

CC BY-SA 3.0
2014-05-13T20:16:38.353Z
2014-05-13T20:52:04.417Z
2014-05-13T20:52:04.417Z
Lev Reyzin
<blockquote>
  <p>How many regular languages are there whose minimal DFA has exactly $n$ states?</p>
</blockquote>

<p>It seems to me that a closed-form formula should exist, but none is known. Some asymptotic bounds are known:</p>

<p><a href="http://www.cs.umanitoba.ca/~mdomarat/pubs/enum_jalc.pdf" rel="noreferrer"><em>On the number of distinct languages accepted by finite automata with $n$ states</em></a>. M Domaratzki, D Kisman, J Shallit.</p>

CC BY-SA 3.0
2014-11-14T01:23:48.513Z
This is really cool.  I happened to just be thinking about this the other day and I didn't know that others have worked on this.  Thanks for sharing.  :)
Michael Wehar
CC BY-SA 3.0
2014-11-21T12:54:18.780Z
Why do you believe that there is a closed formula? I think that's very unlikely.
domotorp
CC BY-SA 3.0
2014-12-07T22:52:14.550Z
See also this question for what is known about that problem: [What is the number of languages accepted by a DFA of size n](http://cstheory.stackexchange.com/questions/7913/what-is-the-number-of-languages-accepted-by-a-dfa-of-size-n)
Hermann Gruber
CC BY-SA 3.0
2014-11-12T07:02:20.347Z
2014-11-12T07:02:20.347Z
mikero
<p>Here is a DFA-related question I'd posted here before, and it's still open as far as I know:</p>
<p>Fix an integer <span class="math-container">$n$</span> and alphabet <span class="math-container">$\Sigma=\{0,1\}$</span>. Define <span class="math-container">$DFA(n)$</span> to be the collection of all finite-state automata on <span class="math-container">$n$</span> states with starting state 1. We are considering <em>all</em> DFAs (not just connected, minimal, or non-degenerate ones); thus, <span class="math-container">$|DFA(n)| = n^{2n}2^n$</span>.</p>
<p>Now consider two strings <span class="math-container">$x,y\in\Sigma^*$</span> and define <span class="math-container">$K_n(x,y)$</span> to be the number of elements of <span class="math-container">$DFA(n)$</span> that accept <em>both</em> <span class="math-container">$x$</span> and <span class="math-container">$y$</span>.</p>
<p>Question: What is the complexity of computing <span class="math-container">$K_n(x,y)$</span>? In particular, can <span class="math-container">$K_n(x,y)$</span> be computed in time <span class="math-container">$poly(n,|x|,|y|)$</span>?</p>
<p>This question has implications for <a href="http://portal.acm.org/citation.cfm?id=1577108" rel="nofollow noreferrer">machine learning</a>.</p>
<p>It was asked here,
<a href="https://cstheory.stackexchange.com/questions/7512/how-many-dfas-accept-two-given-strings">How many DFAs accept two given strings?</a>
and there is some discussion in the comments/answers there. It is still open as far as I know (2021).</p>

CC BY-SA 3.0
2015-01-21T03:42:24.377Z
What is the current status of the problem's complexity?
Ryan Dougherty
CC BY-SA 3.0
2015-01-21T07:25:20.760Z
Jeremiah Blocki had some partial results; this is the state of the knowledge as far as I know:http://www.cs.cmu.edu/~jblocki/Slides/ComputationalComplexityofKn.pdf
Aryeh
CC BY-SA 4.0
2015-01-20T09:01:11.593Z
2021-07-27T19:02:31.100Z
2021-07-27T19:02:31.100Z
Aryeh
<p>("thinking outside the box"...) this is a somewhat contrived problem involving DFAs (have not seen it studied elsewhere) but manifests a theme in TCS that even many apparently "simple" computational objects (like DFAs) can have complex properties, also an aspect/theme embodied in Rices theorem. (in some ways the ultimate "complexity" is "undecidability" aka Turing completeness.)</p>

<p>consider a family of DFAs and an "exponentiation" operator "↑". this operator takes a regular expression (RE) <em>"x↑n"</em> and repeats it $n$ times. ie for any RE $x$ and finite $n$, $x↑n$ is a RE (and therefore also a DFA). this operator is considered in various contexts and in some important problems eg one of the first problems proven EXPSPACE-complete.[1][2]</p>

<p>now consider a family of DFAs $DFA_n$ which is built from a single RL expression $DFA'$ (not exactly/strictly a DFA) with embedded instances of the exponentiation operator in the form <em>"↑n"</em> where here <em>"↑n"</em> is a symbol (but otherwise $DFA'$ is a RL/DFA). then for every finite $n$, $DFA_n$, constructed by replacing/substituting the instances of <em>"x↑n"</em> in $DFA'$ by <em>n</em> repeated instances of <em>x</em>, is also a RL (and a DFA). </p>

<p>(now as usual let $\Sigma$ be the language symbol set/alphabet.) claim:</p>

<blockquote>
  <p>the problem "does there exist an $n$ such that $DFA_n ≠ \Sigma*$" is undecidable.</p>
</blockquote>

<p>the claim follows from constructions in [1] where basically a regular expression is constructed using exponentiation that simulates a TM computation on a specific input iff it is not equal to the "full language" $\Sigma*$. the exponentiation is used to reflect the maximum tape width used in the TM computational tableau accepting the word in the language. this construction can also be found in [3]. a halting computation can be found iff there is a finite $n$ tape width for that computational tableau accepting the word.</p>

<p>now, to tie this in more with the question, while this is not widely noted (considered trivial by some), many open problems in TCS/mathematics are tightly connected with undecidability in that given an oracle for the halting problem, they can be "solved".</p>

<p>therefore, in a sense, tying this all together using this basic problem about DFAs that is undecidable, there will <em>always</em> be open problems about DFAs, because there will always be "open" problems about DFAs (such as this one) equivalent to undecidable problems. in fact using Rices theorem in reverse as this construction does in some ways, basically any relatively "simple" yet nontrivial computational property in TCS can be used to construct undecidable problems.</p>

<p>[1] <a href="http://people.csail.mit.edu/meyer/meyer-stockmeyer-word-probs.pdf" rel="nofollow">Word problems requiring exponential time</a> / Stockmeyer &amp; Meyer</p>

<p>[2] Meyer, A.R. and L. Stockmeyer. <a href="http://people.csail.mit.edu/meyer/rsq.pdf" rel="nofollow">The equivalence problem for regular expressions with squaring requires exponential space.</a> 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.</p>

<p>[3] <a href="http://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation" rel="nofollow">Introduction to languages, automata and computation</a> / Hopcroft/Ullman.</p>

CC BY-SA 3.0
2014-05-20T16:47:43.507Z
I think you are confusing the concepts "undecidable" and "open".
Lev Reyzin
CC BY-SA 3.0
2014-05-20T20:52:49.770Z
as conceded it is an uncommon and/or unconventional view to say the least but am not the only one who has espoused it. see eg this [quote by Michel](http://chat.stackexchange.com/transcript/message/12082885#12082885) in this paper [Problems in number theory
from busy beaver competition](http://arxiv.org/pdf/1311.1029v1.pdf). also similar sentiments expressed wrt famous open number theory conjectures on question [a simple problem whose undecidability is unknown](http://cstheory.stackexchange.com/questions/18846/). see also [automated theorem proving vs undecidability](http://wp.me/p2OLTI-6f)
vzn
CC BY-SA 3.0
2014-05-21T17:40:05.760Z
Your "undecidable" problem has no input, so it can't be undecidable.  There is a Turing machine that accepts the empty string if $DFA_n \ne \Sigma^*$ for all $n$ and rejects the empty string otherwise.  In fact, it's one of two specific TMs that I can easily write down; whether we know (or even _can_ know) which of these two TMs is the correct one is immaterial.  Perhaps you mean "The language $\{1^n \mid DFA_n \ne \Sigma^*\}$ is nonrecursive."
Jeffε
CC BY-SA 3.0
2014-05-28T22:18:54.477Z
@JɛﬀE sorry for any confusion; the input is $DFA'$
vzn
CC BY-SA 3.0
2014-05-20T16:39:40.123Z
2014-05-20T16:46:21.227Z
2014-05-20T16:46:21.227Z
vzn
<p>Here is one problem described in the book "A second course in formal languages and automata theory" by Shallit.</p>

<blockquote>
  <p>Let $u$ and $v$ be two distinct words with $|u|=|v|=n$.  What is
  the size of the smallest DFA that accepts $u$ but rejects $v$, or vice versa? </p>
</blockquote>

<p>Robson, in his paper "<a href="http://www.sciencedirect.com/science/article/pii/0020019089902159">Separating strings with small automata</a>" in 1989 proved an upper bound $O(n^{2/5}(\log n)^{3/5})$.  The best known lower bound in $\Omega(\log n)$.</p>

<p>For a survey <a href="http://arxiv.org/pdf/1103.4513.pdf">see this</a>.</p>

CC BY-SA 3.0
2014-05-11T14:50:17.693Z
In my recent talk at BCTCS 2014 at Loughborough University, I offer 100 GBP for any nontrivial progress on this problem.  Oh, and there are other open problems listed there, too!  See https://cs.uwaterloo.ca/~shallit/Talks/bc4.pdf .
Jeffrey Shallit
CC BY-SA 3.0
2014-05-12T00:54:31.690Z
I'll accept this since it was the first, but they are all great answers. Thanks everyone and keep em coming!
Canadian goose
CC BY-SA 3.0
2015-12-29T01:40:12.320Z
Now in Wikipedia as https://en.wikipedia.org/wiki/Separating_words_problem
David Eppstein
CC BY-SA 4.0
2020-07-24T06:45:27.403Z
Now upper bound is about $n^{1/3}$: https://arxiv.org/abs/2007.12097
domotorp
CC BY-SA 3.0
2014-05-11T03:41:02.527Z
2014-05-11T03:41:02.527Z
Hsien-Chih Chang 張顯之
<p>After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don't mean generalisations of DFAs but the original unmodified DFAs we study in undergrad.</p>

<p>This is a vague question but I hope you get the idea. I want to understand if it is fair to say that we completely understand DFAs. So I really mean questions that are inherently about DFAs, not problems artificially made to look like a problem about DFAs. Let me give an example of such a problem. Let L be the empty language if P=NP and some fixed non-regular language if P is not NP. Can L be accepted by a DFA? This question is about DFAs, but it isn't about them in spirit. I hope my point is clear and I don't get pedantic non-answers from people.</p>

<p>In short is it fair to say</p>

<blockquote>
  <p>We essentially completely understand DFAs.</p>
</blockquote>

<p>I am sorry if it turns out that this is a huge area of research that I was not aware of and I have just insulted an entire community of people.</p>

CC BY-SA 3.0
2014-05-11T03:27:04.947Z
The first open problem came to my mind is whether Černý conjecture is true. http://en.wikipedia.org/wiki/Synchronizing_word and http://www.liafa.jussieu.fr/~jep/Problemes/Cerny.html The following blog post might be interesting for you as well: http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/
Abuzer Yakaryilmaz
CC BY-SA 3.0
2014-05-11T03:27:44.567Z
Does open problems about NFAs and regular expressions count?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-05-11T04:51:35.263Z
@Hsien-Chih: let's be as restrictive as possible in interpreting the question. I had assumed that there are no open problems left, but the answers show this is not true.
Canadian goose
CC BY-SA 3.0
2014-05-12T11:55:43.200Z
DFAs and regular expressions are equivalent. NFAs and DFAs are equivalent in expressive power, although an NFA may have far fewer states than its corresponding DFA.
chepner
CC BY-SA 3.0
2014-05-13T22:14:40.837Z
@chepner Although DFAs, NFAs, and regexen are equivalent in expressive power, that by no means indicates that knowing everything about one implies knowing everything about the other. For example, knowing how to minimize a DFA doesn't directly tell you how to minimize an NFA -- which is in fact [quite a difficult problem](https://dl.acm.org/citation.cfm?id=1268091)!
Daniel Wagner
CC BY-SA 3.0
2014-05-20T04:44:53.000Z
actually this could be regarded as quite a broad question given that a "local" behavior of a TM on a tape "approaches" that of DFA computation. or from another pov it is surely likely to be able to come up with some DFA-related construction/question that expresses Turing complete computation... might post on it later if see/remember one...
vzn
<soft-question><open-problem><dfa>
Are there any open problems left about DFAs?
Canadian goose
# Are there any open problems left about DFAs?

(Asked by: username_0 on 2014-05-11)

After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don't mean generalisations of DFAs but the original unmodified DFAs we study in undergrad.

This is a vague question but I hope you get the idea. I want to understand if it is fair to say that we completely understand DFAs. So I really mean questions that are inherently about DFAs, not problems artificially made to look like a problem about DFAs. Let me give an example of such a problem. Let L be the empty language if P=NP and some fixed non-regular language if P is not NP. Can L be accepted by a DFA? This question is about DFAs, but it isn't about them in spirit. I hope my point is clear and I don't get pedantic non-answers from people.

In short is it fair to say

> We essentially completely understand DFAs.

I am sorry if it turns out that this is a huge area of research that I was not aware of and I have just insulted an entire community of people.

**Tags:** soft-question, open-problem, dfa

> **Comments:**
> **username_1**: The first open problem came to my mind is whether Černý conjecture is true. http://en.wikipedia.org/wiki/Synchronizing_word and http://www.liafa.jussieu.fr/~jep/Problemes/Cerny.html The following blog post might be interesting for you as well: http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/  
> **username_2**: Does open problems about NFAs and regular expressions count?  
> **username_0**: @Hsien-Chih: let's be as restrictive as possible in interpreting the question. I had assumed that there are no open problems left, but the answers show this is not true.  
> **username_3**: DFAs and regular expressions are equivalent. NFAs and DFAs are equivalent in expressive power, although an NFA may have far fewer states than its corresponding DFA.  
> **username_4**: @username_3 Although DFAs, NFAs, and regexen are equivalent in expressive power, that by no means indicates that knowing everything about one implies knowing everything about the other. For example, knowing how to minimize a DFA doesn't directly tell you how to minimize an NFA -- which is in fact [quite a difficult problem](https://dl.acm.org/citation.cfm?id=1268091)!  
> **username_5**: actually this could be regarded as quite a broad question given that a "local" behavior of a TM on a tape "approaches" that of DFA computation. or from another pov it is surely likely to be able to come up with some DFA-related construction/question that expresses Turing complete computation... might post on it later if see/remember one...  

---

## 10 answers

### Answer by username_2 on 2014-05-11. Score: 63 | Accepted answer

Here is one problem described in the book "A second course in formal languages and automata theory" by Shallit.

> Let $u$ and $v$ be two distinct words with $|u|=|v|=n$. What is
> the size of the smallest DFA that accepts $u$ but rejects $v$, or vice versa?

Robson, in his paper "[Separating strings with small automata](http://www.sciencedirect.com/science/article/pii/0020019089902159)" in 1989 proved an upper bound $O(n^{2/5}(\log n)^{3/5})$. The best known lower bound in $\Omega(\log n)$.

For a survey [see this](http://arxiv.org/pdf/1103.4513.pdf).

> **Comments:**
> **username_6**: In my recent talk at BCTCS 2014 at Loughborough University, I offer 100 GBP for any nontrivial progress on this problem.  Oh, and there are other open problems listed there, too!  See https://cs.uwaterloo.ca/~shallit/Talks/bc4.pdf .  
> **username_0**: I'll accept this since it was the first, but they are all great answers. Thanks everyone and keep em coming!  
> **username_8**: Now in Wikipedia as https://en.wikipedia.org/wiki/Separating_words_problem  
> **username_16**: Now upper bound is about $n^{1/3}$: https://arxiv.org/abs/2007.12097  

---

### Answer by username_6 on 2014-05-11. Score: 48

Here's a very simple decision problem about DFA's. Given a DFA M, does M accept the base-2 representation of at least one prime number?

Currently, we don't even know if this problem is recursively solvable.

If it is recursively solvable, and we had an algorithm for it, we could resolve the longstanding open problem about whether there are any Fermat primes (primes of the form $2^{2^n} + 1$) larger than the largest known one, 65537. (Because any prime with base-2 representation of the form $1 0^+ 1$ must be a Fermat prime.)

> **Comments:**
> **username_5**: there are various other conjectures in number theory that relate to periods eg [Erdos Discrepancy problem](http://en.wikipedia.org/wiki/%C2%B11-sequence#Erd.C5.91s_discrepancy_problem) & tieing some into DFA formulations seems possible in other cases too, a possible research program for someone...  
> **username_7**: Do I understand it correctly that if we had an algorithm for this problem, this would also solve Sierpinski's problem and the Riesel problem? (https://en.wikipedia.org/wiki/Sierpinski_number, https://en.wikipedia.org/wiki/Riesel_number)  
> **username_6**: Yes, username_7, that is the case.  

---

### Answer by username_8 on 2014-05-11. Score: 44

The Černý conjecture is still open and important. It is about DFAs that have a [synchronizing word](https://en.wikipedia.org/wiki/Synchronizing_word) (a word with the property that two copies of the automaton started in different states always end up in the same state as each other after both processing the word), and asks whether (for $n$-state automata) the length of the shortest such word is always at most $(n-1)^2$. The best proven bounds are of the form $O(n^3)$.

> **Comments:**
> **username_8**: Sorry, username_1, didn't notice your comment before posting this as an answer. But I do believe it deserves to be an answer and not just a comment...  
> **username_1**: No problem :) I think the second open problem that I linked also looks quite interesting.  
> **username_9**: I know this is a famous question, but is there a quick explanation why it is an important one? What would we learn if the bound really is $(n-1)^2$ rather than $n^3/6$?  
> **username_10**: @SashoNikolov It can be of practical interest to be able to reset a system to a known state without having to observe it (a satellite for instance), using the least number of actions.  
> **username_8**: Yes, I first learned of this problem through the work of Natarajan on designing components of assembly lines that mechanically force the parts on them to be in certain geometric orientations. Shorter reset sequences (in an automaton representing potential reorientation steps) = shorter assembly lines.  

---

### Answer by username_12 on 2014-05-15. Score: 24

**Title:** Intersection non-emptiness for two DFA's

**Description:** Given two DFA's $D\_1$ and $D\_2$, does there exist a string $x$ such that $D\_1$ and $D\_2$ both accept $x$?

**Open Problem:** Can we solve intersection non-emptiness for two DFA's in $o(n^2)$ time?

If we could solve this problem in $O(n^{\delta})$ time where $\delta$ < 2, then the strong exponential time hypothesis would be refuted.

**Explanation:** [Deciding emptiness of intersection of regular languages in subquadratic time](https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time)

You might find this helpful: <http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/>

Have a great day! :)

> **Comments:**
> **username_5**: hi MW glad you noticed this question. recently cited you on this other question re [separating P/L](http://cstheory.stackexchange.com/a/22466/7884). as you have recently proven, the above question (upper bounds on complexity of solving intersection non-emptiness of multiple DFAs) is closely related to (the major open problem of) separating P/NL.  
> **username_12**: Thank you very much!  Who are you username_5?  I went to your blog and looked around, but couldn't figure it out.  
> **username_12**: **Note:** the smallest string accepted by $D_1$ and $D_2$ has length $\Omega(n^2)$ in the worst case.  

---

### Answer by username_11 on 2014-05-11. Score: 20

I want to point out the another research problem, which concerns the interplay of very basic concepts about DFAs.

It is well known that any n-state NFA can be converted into an equivalent DFA having at most $2^n$ states. This is best possible in the worst case, in the sense that there are regular languages of nondeterministic state complexity n (i.e., the number of states in a minimal NFA), but of deterministic state complexity $2^n$. There are also examples of language families, where nondeterminism can save a quadratic factor, and cases where nondeterminism does not help to save any states at all. Thus a natural question is the following:

**Magic number problem**

Is there, for each $\alpha$ between $n$ and $2^n$, a regular language $L\_n$ such that the gap between nondeterministic state complexity and deterministic state complexity is exactly $\alpha$?

If we completely understand the powerset construction and the Myhill-Nerode relation from a mathematical perspective, then I'll expect that one is able to construct such languages for each $\alpha$, or alternatively to specify the values of $\alpha$ for which this is impossible (if such values exist, these are referred to as "magic numbers").

It is known that there are magic numbers for input alphabet size $1$, and, since 2009, that there are no magic numbers if the alphabet size is at least $3$. But if I am not mistaken, the case of binary alphabets is still open.

Galina Jirásková. Magic numbers and ternary alphabet. In: 13th International Conference on Developments in Language Theory (DLT 2009), volume 5583 of Lecture Notes in Computer Science, pages 300–311.

> **Comments:**
> **username_6**: It's a great problem!   But whoever invented the term "magic number" should be shot.  

---

### Answer by username_13 on 2014-05-11. Score: 13

Minimal cover automata is one of a related stuff. Given a finite language $L$, we can obtain a minimal DFA for $L$. But if we relax requirements of DFA we can find smaller ones. We know that longest word in a finite language $L$ has length $l$. Define DFCA as a DFA which accepts only words in $L$ or possibly words which are longer than $l$. Then this DFCA can has smaller size than DFA for $L$. In practice checking a length of a word is not matter. If we have a smaller DFCA which accepts original ones we simply can reject words with length larger than $l$. There has been some research on this class (introduced at 2001), and e.g there is an $O(n^2)$ [algorithm](http://www.dcc.fc.up.pt/~rvr/resources/Aulas-Babel/MAPI-AA/2002_Campeanu.pdf) for finding minimal DFCA. An optimal running time algorithm is not known yet. Also there are other aspects of DFA that we can consider them about DFCA.


---

### Answer by username_14 on 2014-05-13. Score: 12

Here's an open problem relating DFA and machine learning theory: are uniformly random (random transitions and accept/reject behavior) DFA learnable in the PAC model?

Note: we think arbitrary DFA are not learnable b/c of [cryptographic hardness](http://robotics.upenn.edu/~mkearns/papers/crypto.pdf) results. For random DFA, we only have [SQ lower bounds](http://www.levreyzin.com/papers/AngluinEKR10.pdf), which are not as strong.


---

### Answer by username_15 on 2014-11-12. Score: 7

> How many regular languages are there whose minimal DFA has exactly $n$ states?

It seems to me that a closed-form formula should exist, but none is known. Some asymptotic bounds are known:

[*On the number of distinct languages accepted by finite automata with $n$ states*](http://www.cs.umanitoba.ca/~mdomarat/pubs/enum_jalc.pdf). M Domaratzki, D Kisman, J Shallit.

> **Comments:**
> **username_12**: This is really cool.  I happened to just be thinking about this the other day and I didn't know that others have worked on this.  Thanks for sharing.  :)  
> **username_16**: Why do you believe that there is a closed formula? I think that's very unlikely.  
> **username_11**: See also this question for what is known about that problem: [What is the number of languages accepted by a DFA of size n](http://cstheory.stackexchange.com/questions/7913/what-is-the-number-of-languages-accepted-by-a-dfa-of-size-n)  

---

### Answer by username_17 on 2015-01-20. Score: 5

Here is a DFA-related question I'd posted here before, and it's still open as far as I know:

Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering *all* DFAs (not just connected, minimal, or non-degenerate ones); thus, $|DFA(n)| = n^{2n}2^n$.

Now consider two strings $x,y\in\Sigma^\*$ and define $K\_n(x,y)$ to be the number of elements of $DFA(n)$ that accept *both* $x$ and $y$.

Question: What is the complexity of computing $K\_n(x,y)$? In particular, can $K\_n(x,y)$ be computed in time $poly(n,|x|,|y|)$?

This question has implications for [machine learning](http://portal.acm.org/citation.cfm?id=1577108).

It was asked here,
[How many DFAs accept two given strings?](https://cstheory.stackexchange.com/questions/7512/how-many-dfas-accept-two-given-strings)
and there is some discussion in the comments/answers there. It is still open as far as I know (2021).

> **Comments:**
> **username_18**: What is the current status of the problem's complexity?  
> **username_17**: Jeremiah Blocki had some partial results; this is the state of the knowledge as far as I know:http://www.cs.cmu.edu/~jblocki/Slides/ComputationalComplexityofKn.pdf  

---

### Answer by username_5 on 2014-05-20. Score: -3

("thinking outside the box"...) this is a somewhat contrived problem involving DFAs (have not seen it studied elsewhere) but manifests a theme in TCS that even many apparently "simple" computational objects (like DFAs) can have complex properties, also an aspect/theme embodied in Rices theorem. (in some ways the ultimate "complexity" is "undecidability" aka Turing completeness.)

consider a family of DFAs and an "exponentiation" operator "↑". this operator takes a regular expression (RE) *"x↑n"* and repeats it $n$ times. ie for any RE $x$ and finite $n$, $x↑n$ is a RE (and therefore also a DFA). this operator is considered in various contexts and in some important problems eg one of the first problems proven EXPSPACE-complete.[1][2]

now consider a family of DFAs $DFA\_n$ which is built from a single RL expression $DFA'$ (not exactly/strictly a DFA) with embedded instances of the exponentiation operator in the form *"↑n"* where here *"↑n"* is a symbol (but otherwise $DFA'$ is a RL/DFA). then for every finite $n$, $DFA\_n$, constructed by replacing/substituting the instances of *"x↑n"* in $DFA'$ by *n* repeated instances of *x*, is also a RL (and a DFA).

(now as usual let $\Sigma$ be the language symbol set/alphabet.) claim:

> the problem "does there exist an $n$ such that $DFA\_n ≠ \Sigma\*$" is undecidable.

the claim follows from constructions in [1] where basically a regular expression is constructed using exponentiation that simulates a TM computation on a specific input iff it is not equal to the "full language" $\Sigma\*$. the exponentiation is used to reflect the maximum tape width used in the TM computational tableau accepting the word in the language. this construction can also be found in [3]. a halting computation can be found iff there is a finite $n$ tape width for that computational tableau accepting the word.

now, to tie this in more with the question, while this is not widely noted (considered trivial by some), many open problems in TCS/mathematics are tightly connected with undecidability in that given an oracle for the halting problem, they can be "solved".

therefore, in a sense, tying this all together using this basic problem about DFAs that is undecidable, there will *always* be open problems about DFAs, because there will always be "open" problems about DFAs (such as this one) equivalent to undecidable problems. in fact using Rices theorem in reverse as this construction does in some ways, basically any relatively "simple" yet nontrivial computational property in TCS can be used to construct undecidable problems.

[1] [Word problems requiring exponential time](http://people.csail.mit.edu/meyer/meyer-stockmeyer-word-probs.pdf) / Stockmeyer & Meyer

[2] Meyer, A.R. and L. Stockmeyer. [The equivalence problem for regular expressions with squaring requires exponential space.](http://people.csail.mit.edu/meyer/rsq.pdf) 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.

[3] [Introduction to languages, automata and computation](http://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation) / Hopcroft/Ullman.

> **Comments:**
> **username_14**: I think you are confusing the concepts "undecidable" and "open".  
> **username_5**: as conceded it is an uncommon and/or unconventional view to say the least but am not the only one who has espoused it. see eg this [quote by Michel](http://chat.stackexchange.com/transcript/message/12082885#12082885) in this paper [Problems in number theory from busy beaver competition](http://arxiv.org/pdf/1311.1029v1.pdf). also similar sentiments expressed wrt famous open number theory conjectures on question [a simple problem whose undecidability is unknown](http://cstheory.stackexchange.com/questions/18846/). see also [automated theorem proving vs undecidability](http://wp.me/p2OLTI-6f)  
> **username_19**: Your "undecidable" problem has no input, so it can't be undecidable.  There is a Turing machine that accepts the empty string if $DFA_n \ne \Sigma^*$ for all $n$ and rejects the empty string otherwise.  In fact, it's one of two specific TMs that I can easily write down; whether we know (or even _can_ know) which of these two TMs is the correct one is immaterial.  Perhaps you mean "The language $\{1^n \mid DFA_n \ne \Sigma^*\}$ is nonrecursive."  
> **username_5**: @JɛﬀE sorry for any confusion; the input is $DFA'$  

---

