Skip to main content
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 ...
Denis's user avatar
  • 8,853
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 ...
chazisop's user avatar
  • 3,796
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 ...
Andrej Bauer's user avatar
  • 28.9k
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 ...
Aryeh's user avatar
  • 10.5k
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)\...
David's user avatar
  • 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 ...
Jeffrey Shallit's user avatar
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 ...
Jeffrey Shallit's user avatar
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 ...
Denis's user avatar
  • 8,853
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 $...
J.-E. Pin's user avatar
  • 4,831
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$ ...
Sylvain's user avatar
  • 3,374
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 ...
Michaël Cadilhac's user avatar
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 ...
J.-E. Pin's user avatar
  • 4,831
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 ...
domotorp's user avatar
  • 14.1k
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 ...
Shaull's user avatar
  • 5,646
12 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 ...
Jeffrey Shallit's user avatar
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 ...
Denis's user avatar
  • 8,853
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 = \{...
Marzio De Biasi's user avatar
12 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 $...
Marzio De Biasi's user avatar
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 ...
Abuzer Yakaryilmaz's user avatar
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 ...
ricardorr's user avatar
  • 541
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 ...
Michaël Cadilhac's user avatar
11 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 ...
Shaull's user avatar
  • 5,646
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 ...
J.-E. Pin's user avatar
  • 4,831
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 ...
Michael Kay's user avatar
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 ...
Thomas Klimpel's user avatar
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, ...
Neal Young's user avatar
  • 10.8k
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 ...
Shaull's user avatar
  • 5,646
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 ...
Joshua Grochow's user avatar
10 votes
Accepted

Converting 2-ambiguous NFA to unambiguous NFA

I think that this is in fact not possible, thanks to the (recent and difficult!) ICALP'22 results of Göös et al.. They show that there are UFAs $A_1$ and $A_2$ with $n$ states such that the language $...
a3nm's user avatar
  • 9,269
9 votes
Accepted

Kleene closure of DFA

You asked a similar question some time ago about concatenation. I gave the references back then and they still apply here. See Yu, Zhuang, and K. Salomaa in their paper, "The state complexities of ...
Jeffrey Shallit's user avatar

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