Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Hot answers tagged

341

I have personally enjoyed several Aha! moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole. Does Non-determinism Lead to Efficiency? There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. ...


56

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


41

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


39

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


33

There are many good theoretical reasons to study N/DFAs. Two that immediately come to mind are: Turing machines (we think) capture everything that's computable. However, we can ask: What parts of a Turing machine are "essential"? What happens when you limit a Turing machine in various ways? DFAs are a very severe and natural limitation (taking away ...


31

To add one more perspective to the rest of the answers: because you can actually do stuff with finite automata, in contrast with Turing machines. Just about any interesting property of Turing machines are undecidable. On the contrary, with finite automata, just about everything is decidable. Language equality, inclusion, emptiness and universality are all ...


27

State. you need to learn that one can model the world (for certain problems) as a finite state space, and one can think about computation in this settings. This is a simple insight but extremely useful if you do any programming - you would encounter state again and again and again, and FA give you a way to think about them. I consider this to be a sufficient ...


21

Although it is not really the reason they were originally studied, finite automata and the regular languages they recognize are tractable enough that they have been used as building blocks for more complicated mathematical theories. In this context see particularly automatic groups (groups in which the elements can be represented by strings in a regular ...


20

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


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


18

You are asking (at least) two different questions: (a) What parts of theory build on finite automata nowadays? (b) Why were finite automata developed in the first place? I think the best way to address the latter is to look at the old papers, such as: Rabin, Scott, Finite Automata and Their Decision Problems, 1959 Here are the first two paragraphs: ...


16

Another reason is that they're relatively practical theoretical models. A Turing machine, apart from the impossibility of the infinite tape, is kind of an awkward fit for what it's like to program a computer (note that this is not a good analogy to begin with!). PDAs and DFAs however are quite amenable to being models of actual programs in the sense that a ...


16

According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over $\{0,1\}$ does not generate all strings. So your problem is also PSPACE-complete. Here is one way to see that the OP's problem is in PSPACE. Given a DFA $A$ and a regular expression $r$, construct ...


14

Short answer. Given a finite family of regular languages $\mathcal{L} = (L_i)_{1 \leqslant i \leqslant n}$, there is a unique minimal deterministic complete multi-automaton recognizing this family. Details. The case $n = 1$ corresponds to the standard construction and the general case is not much different in spirit. Given a language $L$ and a word $u$, ...


13

There are different algorithms to convert regular expressions to finite automata. You can go directly from regular expressions to DFAs without building any other automaton first by implicitly doing the subset construction while generating the automaton. Another option to directly obtain deterministic automata is to use the method of derivatives. Checking ...


12

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


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


10

As you pointed out, there are several ways to define minimal transducers, but I only know of two mathematically appealing definitions. The first result concerns the reduction of linear representations of recognizable series (= defined by weighted automata). The best reference is Chapter II, Minimization, in one of these two books (the more recent is an ...


10

Check out the "Living Binary Adder" Game here : http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html I used to present this game to my students in the early chapters about DFA/NFA. It illustrates two important things in Automata Theory: How to transform a mental process into a simple mechanical one What abstraction really means. Two states, ...


9

The concept of DFAs is very useful for designing efficient solutions to many types of problems. One example is networking. Every protocol can be implemented as a state machine. Implementing the solution this way makes the code simpler and simpler means a lower defect rate. It also means that changes to the code are easier and have a lower impact, again ...


9

Yes, there are some cases of the DFA non emptiness insersection problem that are inside P. My master's thesis is devoted to this question, but unfortunately it is in French. However, most of the results have appeared here in $[2]$. When the alphabet is unary, then the problem is L-complete when each DFA has at most two final states, and NP-complete ...


9

If I had to do this in practice, I would use a SAT solver. The question of whether there is a DFA with $k$ states that accepts $x$ and rejects $y$ can be easily expressed as a SAT instance. For instance, one way is to have $2k^2$ boolean variables: $z_{s,b,t}$ is true if the DFA transitions from state $s$ to state $t$ on input bit $b$. Then add some ...


8

The other contributor deleted his answer, maybe to let me extend my above comment, so here it is. Let $T$ be a possibly nondeterministic transducer, and $L$ be a regular language. Modify $T$ into a transducer $T'$ that checks that its input is in $L$ (by, e.g., changing the state set into the Cartesian product of the state sets of $T$ and $L$, and ...


8

Take a look at this MFCS 2013 paper, which studies compositionality in automata. Perhaps it will help.


7

Recall that, in the case of finite state automata, the notion of a minimal automaton is usually meant for deterministic automata only; you can define it for non-deterministic ones, but then you lose two important properties: canonicity (there is a unique minimal deterministic complete automaton for a given regular language, up to state renaming) and the ...


7

According to Ishigami Y., Tani S. (1993) The VC-dimensions of finite automata with n states, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , the VC-dimension of the concept class of $n$-state DFAs over an alphabet of size $k$ is $$ d=d(n,k) := (k-1+o(1))n\log_2 n.$$ It follows that there are at least $2^d$ distinct $n$-state automata on a $k$-...


7

The precise bound is $2^n$. The lower bound was given in the comments: the state complexity of $A^*a_1A^* \cap \dotsm \cap A^*a_nA^*$ is $2^n$. For the upper bound, it suffices to observe that if $B$ and $C$ are subsets of the alphabet $A$, then the language $B^*CA^* = (B - C)^*CA^*$ is recognised by a 2-state DFA. It follows that the complexity of the ...


6

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.


6

The main conferences where automata are among the main topics are ICALP, LICS, STACS, CSL, MFCS, FSTTCS. If you feel your paper is not strong enough for these conferences (which accept about a quarter of the papers that are sent each year), you can send to conferences which are a little less exigeant. The ICALP submission deadline is soon (in a week), ...


6

Have you tried Brzozowski's algorithm? It's worst-case running time is exponential, but I see some references suggesting that it often performs very well, especially when starting with a NFA that you want to convert to a DFA and minimize. The following paper seems relevant: On the performance of automata minimization algorithms, Marco Almeida, Nelma ...


Only top voted, non community-wiki answers of a minimum length are eligible