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 ...
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 ...
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,...
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 ...
19
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
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
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
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.
16
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 ...
16
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
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
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
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 ...
14
Yes, they are.
First, consider the alphabet $\Sigma_i^3$ whose symbols are triples of digits (stacked one above each other into a pile of three digits). Over this alphabet, we can define a regular language $A'$ where the string formed by the topmost of the three digits belongs to $A$, a regular language $B'$ where the string formed by middle of the three ...
14
Essentially the same argument is made by Andries P.J. van der Walt (1976, Lemma 2.3 and Example 2.9) for the variant of the pumping lemma where $N$ letters are marked and all three of $x$, $y$, $z$ must contain marked letters. See also Autebert, Boasson, and Cousineau (1978) for more properties of abstract families of languages satisfying this variant of ...
13
The identity $(x + y)^* = x^*(yx^*)^*$ is a classical identity of regular expressions, but
it is a nontrivial problem to find a complete set of identities for regular expressions. An infinite complete set was proposed by John Conway and this conjecture was ultimately proved by D. Krob.
J.H. Conway, Regular algebra and finite machines, Chapman and Hall, 1971,...
13
This question generated a lot of literature in the 80's, partly due to a bad approach to the problem. This is a rather long story that I will try to summarize in this answer.
1. The case of finite words
One can find two definitions of a minimal DFA in the literature.
The first one is to define the minimal DFA of a regular language as the complete DFA ...
13
It is NP-hard for $k=3$.
The reduction is from 3-SAT-(2,2), which means that every clause contains $3$ literals and every literal occurs in at most $2$ clauses.
First of all, for simplicity, let's admit honestly that this problem has not much to do with automata.
Your problem is equivalent to the following:
Given an edge-colored digraph where each color ...
12
The bounds...
We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the same paper.
...cannot be substantially improved
There can be a subexponential gap between $Cov(M)+Cov(N)$ and $NFA(L)$. The following example, and the proof ...
12
In general, $\omega$-regular languages may not have a unique minimal DBW. For example, the language "infinitely many a's and infinitely many b's" has two 3-state DBWs (in the picture replace $\neg a$ by $b$):
As you can see, they are not topologically equivalent.
Hence, the minimization problem is harder than the finite case, and in fact, it is NP-complete....
12
Expanding the comment: a natural hierarchy is the one induced by the number of states of the DFA.
We can define $\mathcal{L}_n = \{ L \mid \text{ exists an n-states DFA D s.t. } L(D) = L \}$
($D = \{Q, \Sigma, \delta, q_0, F \}$, $|Q| = n$ )
Clearly $\mathcal{L}_n \subseteq \mathcal{L}_{n+1}$ (simply use dead states)
To show the proper inclusion $\...
12
No, the exponential lower bound for determinization holds already for unambiguous NFAs. This is obtained as follows:
Consider the alphabet $\{a,b\}$, and the language:
$$L_k=\{w\in \{a,b\}^*:\text{the $k$-th before last letter in }w\text{ is }b\}$$
It's easy to construct an unambiguous NFA for $L_k$: the NFA guesses when the $k$ before last letter is, and ...
11
So people keep nagging me to post this even though it only solves a simplified
version of the problem. Okay then :)
At the end of this, I will put some of what I learned from the paper of Ibarra and Trân, and why that method breaks down on our general problem, but perhaps still gives some useful information.
But first, we'll look at the simpler problem of ...
Only top voted, non community-wiki answers of a minimum length are eligible