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 ...
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 ...
27
votes
Accepted
Number of words of length n in a context-free language
Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:
Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
Or there ...
18
votes
Irreducible languages
There is the notion of primality of a language. It asks whether L can be written as $L_1 \cdot L_2$ where neither factor contains the empty word. A language is prime if it cannot be written in this ...
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}...
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 ...
16
votes
Accepted
Decide the existence of a string homomorphism
It's discussed in one of the very first papers about strings and complexity, namely, Dana Angluin, Finding patterns common to a set of strings, J. Comput. System Sci.
21 (1980), 46-62. Look at ...
16
votes
Accepted
What is the name of a function $f$ such that $f(x,y) \in L \iff x\in L \wedge y \in L$?
They are typically called AND-functions. (I'm not joking.) Indeed, this concept has been considered before, and that's what people call them. See, for example, the book by Kobler, Schoning, and Toran ...
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
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 ...
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$ ...
14
votes
Irreducible languages
Another paper to look at:
Kai Salomaa, "Language Decompositions, Primality, and Trajectory-Based Operations", 2008.
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 ...
13
votes
Accepted
Translation of context-free parsing into SAT
(I guess the important word in the original question is ``published''.) There is such an encoding of context-free parsing (more exactly of CYK-style parsing) in Roland Axelsson, Keijo Heljanko, and ...
13
votes
Accepted
"Embedding" a language in itself
This question is related to the so called insertion systems.
An insertion system is a special type of rewriting system whose rules are of the form $1 \rightarrow r$ for all $r$ in a given language $R$...
13
votes
Accepted
Is the Set of all Primitive Words a Prime Language?
The answer is yes. Suppose we have a factorization $Q = A\cdot B$.
One easy observation is that $A$ and $B$ must be disjoint (since for $w\in A\cap B$ we get $w^2\in Q$). In particular, only one of $...
13
votes
Accepted
Ambiguity of regular expressions
Yes, every regular expression can be converted into an unambiguous one by converting to a DFA and then to a regular expression. And no, there aren't any inherently ambiguous regular languages in the ...
12
votes
Accepted
Bounds on size of self-concatenation of Finite Languages
You can show $ |L|^i $ is a tight upper bound by using the following language:
$ L = \{ ab,aab,aaab,\ldots,a^kb \mid k \geq 1 \}. $
Any concatenation gives a new string. For a lower bound, I can ...
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$ ...
12
votes
Accepted
What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?
If $\mathrm{P\subseteq CSL}$, then $\mathrm{P\subseteq DSPACE}(n^2)$. By a padding argument, this implies
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$
for every ...
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 ...
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 ...
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 ...
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 ...
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 ...
11
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 ...
11
votes
Accepted
Size of complement of context-free language
From the proof that determining if a CFL ${L}$ = $\Sigma^*$ is undecidable, the set of strings $ID_0\#ID_1^R\#ID_2\#ID_3^R\#\ldots\#ID_t$ where $ID_0,ID_1,\ldots,ID_t$ is a list of the configurations ...
11
votes
Accepted
Is the complement of { www | … } context-free?
Still CFL I believe, with an adaptation of the classical proof. Here's a sketch.
Consider $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$, which is the complement of $\{www\}$, with the ...
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 $...
11
votes
Accepted
Example of an context-sensitive language with a specific number of words of length $n$
The language
$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$
is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
fl.formal-languages × 420automata-theory × 179
context-free × 76
reference-request × 68
grammars × 68
regular-language × 65
cc.complexity-theory × 32
regular-expressions × 29
computability × 22
parsing × 21
ds.algorithms × 18
co.combinatorics × 13
dfa × 13
omega-language × 13
lo.logic × 11
pl.programming-languages × 11
algebra × 11
decidability × 11
turing-machines × 10
space-bounded × 9
nondeterminism × 9
complexity-classes × 8
time-complexity × 8
tree × 8
open-problem × 6