44
votes
Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?
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 ...
- 7,653
32
votes
Accepted
Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?
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 ...
- 3,741
23
votes
Accepted
Deciding emptiness of intersection of regular languages in subquadratic time
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 ...
- 4,900
20
votes
Automata learning without counterexamples
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 ...
- 10k
19
votes
Accepted
Quadratic relationship between nondeterministic and deterministic space?
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 ...
- 6,888
18
votes
Accepted
Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?
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 ...
- 22.3k
18
votes
Accepted
Is Hartmanis-Stearns conjecture settled by this article?
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 ...
- 6,888
17
votes
Accepted
Regular versus TC0
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}...
- 992
17
votes
Accepted
For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?
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)\...
- 188
16
votes
Accepted
What notable automaton models have polynomially-decidable containment?
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 ...
- 5,424
16
votes
Hierarchies in regular languages
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
$...
- 4,721
15
votes
Regular versus TC0
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 ...
- 14.8k
15
votes
Accepted
Regular language that discriminates between two deterministic CFGs
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 ...
- 3,816
14
votes
What notable automaton models have polynomially-decidable containment?
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 ...
- 7,653
14
votes
Accepted
Are regular languages closed under addition?
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 ...
- 50.2k
14
votes
Accepted
Novel proof of pumping lemma for regular languages
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$ ...
- 3,314
13
votes
Minimizing Automata accepting $\omega$-words (i.e. infinite words)
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 ...
- 4,721
13
votes
Accepted
Complexity of the problem of words with fewest distinct letters accepted by a finite automaton
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 ...
- 13.5k
12
votes
Accepted
Lower bound for NFA accepting 3 letter language
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 ...
- 5,424
12
votes
Accepted
Minimizing Automata accepting $\omega$-words (i.e. infinite words)
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$ ...
- 5,261
12
votes
Hierarchies in regular languages
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 = \{...
- 22.3k
12
votes
Determinising unambiguous automata without exponential blowup
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 ...
- 5,261
11
votes
What notable automaton models have polynomially-decidable containment?
A Non deterministic XOR automaton (NXA) fits your question.
A NXA $M$ is essentially an NFA, but a word $w\in \Sigma^*$ is said to be in $L(M)$ if it is accepted by an odd number of paths (Xor ...
- 9,378
11
votes
Conjecture about two counters automata
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 ...
- 311
11
votes
Accepted
Can we approximate the number of words accepted by an NFA?
There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length $n$ accepted by a NFA in the general case (without restricting to the acyclic ...
- 521
11
votes
Accepted
computing maximal bit density over a FSM
First, you mean "sup" rather than "max", because it is easy to construct examples of regular languages, such as 00(011)*00 where there is no max. (The sup may not be attained.)
Second, by "FSM" I ...
- 6,888
11
votes
Accepted
Finding the smallest DFA that separates two words without using brute force search?
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 ...
- 10.4k
11
votes
Accepted
Is there a survey of the field of quantum automata?
You can check the recent survey by Ambainis and Yakaryilmaz: Automata and Quantum Computing. It is comprehensive and points the essential literature with some open questions.
Moreover, here is a list ...
- 3,647
11
votes
Accepted
Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$
You don't need nondeterminism or multiple heads. Even a 2DPDA can accept this language: push 2 counters per symbol while scanning from left endmarker to right; then pop 3 per symbol while scanning ...
- 6,888
11
votes
Accepted
On the realisation of monoids as syntactic monoids of languages
It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without ...
- 7,653
Only top scored, non community-wiki answers of a minimum length are eligible