# Tag Info

### 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 ...
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 ...
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 ...

### 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 ...
Accepted

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 ...
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 ...
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$ ...
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 ...