Are there any open problems left about DFAs?

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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

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

Have a great day! :)

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

It was asked here, 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).

Answer 10

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