346
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. ...
44
To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata.
Indeed, the main difference between the two models is that with finite automata, we expect to treat data that is bigger than the state space, and Turing Machine are a model for the other way around (state space >> data) by making the ...
34
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 ...
32
There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or even forgotten.
Historically, the Turing Machine is perhaps the most intuitive model of several developed trying to answer the Entscheidungsproblem. This is ...
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 ...
24
Simple answer: If there does exist a more efficient algorithm that runs in $O(n^{\delta})$ time for some $\delta < 2$, then the strong exponential time hypothesis would be refuted.
We will prove a stronger theorem and then the simple answer will follow.
Theorem: If we can solve the intersection non-emptiness problem for two DFA's in $O(n^{\delta})$ time,...
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
Consider password automata: for each $w\in\{0,1\}^n$, the DFA $M_w$ accepts the language $\{w\}$. In this case, a membership query is the same as an equivalence query --- and clearly, you'll need exponentially many of these to find the "needle in the haystack". (This is even if the learner knows in advance that the target automaton is of this form.) For a ...
18
State complexity is really about concise description of an object (in this case, a regular language), not about computational complexity. The general topic is called "descriptional complexity" in the literature and draws its inspiration, in part, from the classic 1971 paper of Meyer and Fischer entitled "Economy of Expression by Automata, Grammars, and ...
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:
...
18
Let me provide you with an algorithm for recursively constructing an infinite state machine to decide any language $L \subseteq \{0,1\}^\ast$ that you like.
Make the initial state accept if the empty string is in the language.
Create two states for the strings 0 and 1, which the initial state branches to depending on whether the first symbol is 0 or 1. ...
18
Perhaps I found some relevant information in:
Jean-Michel Autebert, Jean Berstel, Luc Boasson; Context-Free Languages and Pushdown Automata; Handbook of Formal Languages; 1997, pp 111-174
DPDAs without $\epsilon$-transitions are known as realtime deterministic pushdown automata.
They are less powerful than DPDAs, for example
$L = \{ a^n b^p c a^n \mid ...
18
In my paper with Domaratzki and Kisman, "On the number of distinct languages accepted by finite automata with n states" published in J. Automata, Languages, and Combinatorics 7 (2002) we proved that if $G_k (n)$ is the number of distinct languages accepted by NFA's with $n$ states over a $k$-letter alphabet, and $g_k (n)$ is similarly the number of distinct ...
18
First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn".
Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in real time; in other words, the TM must compute the n'th digit in n time.
Third, the result of Adamczewski et al. is only about finite automata and deterministic ...
17
Take $S_5$ as alphabet and
$$L= \{ \sigma_1\cdots \sigma_n \in S_5^*\mid \sigma_1\circ\cdots\circ\sigma_n = \text{Id}\}$$
Barrington proved in [2] that $L$ is $\textrm{NC}^1$-complete for $\textrm{AC}^0$ reduction (and even with a more restrictive reduction actually).
In particular this shows that regular languages are not in $\textrm{TC}^0$ if $\textrm{...
17
This question is addressed in Section 2 of [1], which shows (Theorem 2.6) that the problem is
in P if $L(\alpha)$ is finite;
coNP-complete if $L(\alpha)$ is infinite but bounded (i.e. $L(\alpha)\subseteq w_1^*w_2^*\ldots w_k^*$ for some $w_1,\ldots, w_k$);
PSPACE-complete otherwise.
[1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymanski, On the ...
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 ...
16
There is even a stronger result than your request:
There are exponentially-ambiguous NFAs for which the minimal polynomially-ambiguous NFAs are exponentially larger, and in particular the minimal UFAs.
Check this paper by Hing Leung.
15
Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular languages is strictly contained within the class of visibly pushdown languages. For deterministic visibly pushdown automata, the language inclusion problem can ...
15
Regular languages with unsolvable syntactic monoids are $\mathrm{NC}^1$-complete (due to Barrington; this is the underlying reason behind the more commonly quoted result that $\mathrm{NC}^1$ equals uniform width-5 branching programs). Thus, any such language is not in $\mathrm{TC}^0$ unless $\mathrm{TC}^0=\mathrm{NC}^1$.
My favorite $\mathrm{NC}^1$-...
15
Here is a list of several hierarchies of interest, some of which were already mentioned in other answers.
Concatenation hierarchies
A language $L$ is a marked product of $L_0, L_1, \ldots, L_n$ if
$L = L_0a_1L_1 \cdots a_nL_n$ for some letters $a_1, \ldots, a_n$.
Concatenation hierarchies are defined by alternating Boolean operations and polynomial ...
15
Eryk Kopczyński[1] showed in 2015 that separability (that's the name of your problem) of visibly pushdown languages by regular languages is undecidable. The class of visibly pushdown languages is a strict subset of deterministic CFL.
[1]: Eryk Kopczyński, Invisible Pushdown Languages, LICS'16, available at https://arxiv.org/abs/1511.00289
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$, ...
14
Finite automata in which the initial state is also the unique accepting state have the form $r^∗$, where $r$ is some regular expression. However, as J.-E. Pin points out below, the converse is not true: there are languages of the form $r^*$ which are not accepted by a DFA with a unique accepting state.
Intuitively, given a sequence of states $q_0, \ldots, ...
14
An $\omega$-regular language is actually quite low in the Borel hierarchy (inside $\Delta_3$), a result due to
R. McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521-530.
For a proof and more details, you can look at Chapter 3 of the following book
D. Perrin et J.-É. Pin, Infinite words, ...
14
Let $A = \{1, ..., k\}$ be an ordered alphabet. Then each word on $A^*$ can be viewed as a number in base $k + 1$ (note that $0$ is never used on purpose). Now define
$$
rank(u) = \begin{cases}
u &\text{if $u \in L$} \\
0 &\text{otherwise}
\end{cases}
$$
Then $rank$ preserves the shortlex (or radix) order, which is the order $\leqslant$ on $A^*$ ...
14
I think the IJFCS'05 paper by Leung: Descriptional complexity of nfa of different ambiguity
provides an example with a family of NFA accepting finite languages that involve an exponential blowup for "disambiguation" (in the proof of Theorem 5).
What is more, those automata have a special structure (DFA with multiple initial states).
14
If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment.
A NFA is GFG if there is a strategy $\sigma:A^*\times Q\times A\to \Delta$, that given the prefix read so far and the current state and letter, chooses a transition to go to the next ...
Only top voted, non community-wiki answers of a minimum length are eligible
