# Are there any open problems left about DFAs?

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.

-
The first open problem came to my mind is whether Černý conjecture is true. en.wikipedia.org/wiki/Synchronizing_word and liafa.jussieu.fr/~jep/Problemes/Cerny.html The following blog post might be interesting for you as well: rjlipton.wordpress.com/2009/08/17/… – Abuzer Yakaryilmaz May 11 '14 at 3:27
Does open problems about NFAs and regular expressions count? – Hsien-Chih Chang 張顯之 May 11 '14 at 3:27
@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 May 11 '14 at 4:51
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 May 12 '14 at 11:55
@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! – Daniel Wagner May 13 '14 at 22:14

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

-
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 cs.uwaterloo.ca/~shallit/Talks/bc4.pdf . – Jeffrey Shallit May 11 '14 at 14:50
I'll accept this since it was the first, but they are all great answers. Thanks everyone and keep em coming! – Canadian goose May 12 '14 at 0:54
Now in Wikipedia as en.wikipedia.org/wiki/Separating_words_problem – David Eppstein Dec 29 '15 at 1:40

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

-
there are various other conjectures in number theory that relate to periods eg Erdos Discrepancy problem & tieing some into DFA formulations seems possible in other cases too, a possible research program for someone... – vzn May 14 '14 at 16:31

The Černý conjecture is still open and important. It is about DFAs that have a 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)$.

-
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 May 11 '14 at 4:46
No problem :) I think the second open problem that I linked also looks quite interesting. – Abuzer Yakaryilmaz May 11 '14 at 6:04
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 May 16 '14 at 13:13

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.

-
It's a great problem! But whoever invented the term "magic number" should be shot. – Jeffrey Shallit May 11 '14 at 22:59

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.

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

Have a great day! :)

-
hi MW glad you noticed this question. recently cited you on this other question re separating P/L. 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 May 15 '14 at 15:16
Thank you very much! Who are you vzn? I went to your blog and looked around, but couldn't figure it out. – Michael Wehar May 15 '14 at 19:13
Note: the smallest string accepted by $D_1$ and $D_2$ has length $\Omega(n^2)$ in the worst case. – Michael Wehar Nov 5 '15 at 4:43

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 results. For random DFA, we only have SQ lower bounds, which are not as strong.

-

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

-

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. M Domaratzki, D Kisman, J Shallit.

-
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 Nov 14 '14 at 1:23
Why do you believe that there is a closed formula? I think that's very unlikely. – domotorp Nov 21 '14 at 12:54
See also this question for what is known about that problem: What is the number of languages accepted by a DFA of size n – Hermann Gruber Dec 7 '14 at 22:52

Here is a DFA-related question I'd 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.

-
What is the current status of the problem's complexity? – Ryan Jan 21 '15 at 3:42
Jeremiah Blocki had some partial results; this is the state of the knowledge as far as I know:cs.cmu.edu/~jblocki/Slides/ComputationalComplexityofKn.pdf – Aryeh Jan 21 '15 at 7:25

("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 / Stockmeyer & Meyer

[2] Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.

[3] Introduction to languages, automata and computation / Hopcroft/Ullman.

-
I think you are confusing the concepts "undecidable" and "open". – Lev Reyzin May 20 '14 at 16:47
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 in this paper Problems in number theory from busy beaver competition. also similar sentiments expressed wrt famous open number theory conjectures on question a simple problem whose undecidability is unknown. see also automated theorem proving vs undecidability – vzn May 20 '14 at 20:52
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ε May 21 '14 at 17:40
@JɛﬀE sorry for any confusion; the input is $DFA'$ – vzn May 28 '14 at 22:18