45
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 ...
- 8,598
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,751
25
votes
Theoretical Computer Science vs other Sciences?
As a theoretical computer scientist I am proud of the following achievements of the field.
Logicians figured out that all logical connectives can be build from a single one, paving the road for ...
- 28.3k
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 ...
- 10.3k
19
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)\...
- 308
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,967
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,967
18
votes
Theoretical Computer Science vs other Sciences?
As a TCS researcher, I understand the feeling and feel it too sometimes. I think it is healthy to be able to appreciate the wonder that other sciences have to offer.
We must also keep in mind that it ...
- 8,598
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
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,771
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 ...
- 16.9k
15
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,354
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,946
13
votes
On the realisation of monoids as syntactic monoids of languages
The terminology rigid seems to be relatively new compared to the term disjunctive used in the late 70's (and probably before, I didn't check for earlier references). A subset $P$ of a monoid $M$ is ...
- 4,771
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.9k
13
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,531
12
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 ...
- 8,598
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.6k
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 ...
- 541
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,707
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,967
11
votes
On the realisation of monoids as syntactic monoids of languages
In a more elementary way than Denis's answer, the following is extracted from Pippenger's "Theories of Computability", p.87, and immediate to check.
Definition: Let $M$ be a monoid, and $Y \subseteq ...
- 3,946
11
votes
Existence of an algorithm
A language $L$ is said to be commutative if the following property holds:
for every word $a_1 \dotsm a_n \in L$ and any permutation $\sigma$ on
$\{1, \ldots, n\}$, the word $a_{\sigma(1)} \dotsm ...
- 4,771
11
votes
NP-complete decision problems on deterministic automata
The decision version of the DFA identification problem (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete:
Input: Integer $k$ and sets $...
- 22.6k
11
votes
Theoretical Computer Science vs other Sciences?
I run a small software business producing XML processing tools, so I'm very much a practical engineer rather than a theoretician. It's 50 years since I did my CS degree. And you know, I'm constantly ...
- 211
10
votes
Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?
Andrej Bauer gave one important reason in the comments:
Because sometimes $\infty$ is a better approximation to $10000000000000000000000000000000$ than $10000000000000000000000000000000$.
Let me ...
- 3,033
10
votes
Accepted
What is the motivation behind defining Deterministic Looping Automata?
In a looping automaton, the transition function is not assumed to be total. That is, for a state $q$ and a letter $\sigma$, it could be the case that $\delta(q,\sigma)$ is undefined.
Intuitively, this ...
- 5,531
10
votes
Accepted
Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?
EDIT: Added Lemma 2 which covers all cases asked about.
Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, ...
- 9,595
10
votes
Accepted
Finite-State Automata over a real-valued alphabet
Automata over infinite alphabets have been studied in many contexts (see e.g., this paper as a starting point).
Usually, the model is somewhat different than what you suggest, since just having an ...
- 5,531
10
votes
Theoretical Computer Science vs other Sciences?
My impression from your comments is that perhaps you have just not seen enough theoretical CS to get to some of the kind of content you are excited about in, say, physics.
I'll also point out that you ...
- 36.9k
Only top scored, non community-wiki answers of a minimum length are eligible