# Tag Info

## Hot answers tagged fl.formal-languages

### 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 ...
• 7,653
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,741
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,712

### 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,377
Accepted

• 2,470
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,424
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 ...
• 3,647
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$ ...
• 5,261
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 ...
• 14.8k