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,473
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,731
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 ...
- 5,742
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 ...
- 27.9k
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 ...
- 1,417
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,473
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
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 ...
- 36.4k
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 ...
- 15.6k
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,334
14
votes
Irreducible languages
Another paper to look at:
Kai Salomaa, "Language Decompositions, Primality, and Trajectory-Based Operations", 2008.
- 6,947
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$...
- 4,761
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 $...
- 2,490
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 ...
- 5,649
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,511
12
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,761
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 ...
- 15.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 ...
- 521
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 ...
- 8,473
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,916
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 ...
- 8,556
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 ...
- 3,916
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.5k
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^{\...
- 15.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
Accepted
What is the state complexity of the copy language?
The technique described by Yuval:
Do there exists polynomial size CFG that describe this finite language?
(
you may also read:
Lower bounds on the size of CFGs for specific finite languages
)
...
- 1,085
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,013
10
votes
Accepted
Known and described subclasses of Context-Free Grammars class
Density might be interesting concept for you. The density function is defined as
$$\delta_L(n) := |L\cap \Sigma^n|,$$
where $\Sigma^n$ denotes the set of all strings of length $n$ over $\Sigma$.
...
- 452
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,511
10
votes
Base-k representations of the co-domain of a polynomial - is it context-free?
Of course $k \geq 2$ here.
There once was a manuscript by Horváth that claimed to solve the problem, but it was unclear in several places and to my knowledge was never published.
As far as I know, ...
- 6,947
Only top scored, non community-wiki answers of a minimum length are eligible