# Tag Info

## Hot answers tagged fl.formal-languages

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,223
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.6k
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,223
17 votes
Accepted

• 2,480
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,534
13 votes

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,501

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