69
$\begingroup$

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.

$\endgroup$
7
  • 16
    $\begingroup$ 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/… $\endgroup$ May 11, 2014 at 3:27
  • 1
    $\begingroup$ Does open problems about NFAs and regular expressions count? $\endgroup$ May 11, 2014 at 3:27
  • 1
    $\begingroup$ @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. $\endgroup$ May 11, 2014 at 4:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – chepner
    May 12, 2014 at 11:55
  • 6
    $\begingroup$ @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! $\endgroup$ May 13, 2014 at 22:14

10 Answers 10

63
$\begingroup$

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.

$\endgroup$
4
48
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$
    – vzn
    May 14, 2014 at 16:31
  • 4
    $\begingroup$ 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? (en.wikipedia.org/wiki/Sierpinski_number, en.wikipedia.org/wiki/Riesel_number) $\endgroup$
    – sdcvvc
    May 3, 2017 at 20:56
  • 3
    $\begingroup$ Yes, sdcvvc, that is the case. $\endgroup$ May 4, 2017 at 17:01
44
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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... $\endgroup$ May 11, 2014 at 4:46
  • 2
    $\begingroup$ No problem :) I think the second open problem that I linked also looks quite interesting. $\endgroup$ May 11, 2014 at 6:04
  • 7
    $\begingroup$ 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$? $\endgroup$ May 16, 2014 at 13:13
  • 1
    $\begingroup$ @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. $\endgroup$
    – Denis
    Mar 20, 2017 at 14:10
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 17, 2017 at 1:34
24
$\begingroup$

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! :)

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – vzn
    May 15, 2014 at 15:16
  • $\begingroup$ Thank you very much! Who are you vzn? I went to your blog and looked around, but couldn't figure it out. $\endgroup$ May 15, 2014 at 19:13
  • 2
    $\begingroup$ Note: the smallest string accepted by $D_1$ and $D_2$ has length $\Omega(n^2)$ in the worst case. $\endgroup$ Nov 5, 2015 at 4:43
20
$\begingroup$

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.

$\endgroup$
1
  • 8
    $\begingroup$ It's a great problem! But whoever invented the term "magic number" should be shot. $\endgroup$ May 11, 2014 at 22:59
13
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

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

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

$\endgroup$
2
-3
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ I think you are confusing the concepts "undecidable" and "open". $\endgroup$
    – Lev Reyzin
    May 20, 2014 at 16:47
  • $\begingroup$ 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 $\endgroup$
    – vzn
    May 20, 2014 at 20:52
  • $\begingroup$ 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." $\endgroup$
    – Jeffε
    May 21, 2014 at 17:40
  • $\begingroup$ @JɛffE sorry for any confusion; the input is $DFA'$ $\endgroup$
    – vzn
    May 28, 2014 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.