# Tag Info

## Hot answers tagged formal-languages

19

A TM does not have a register, but a register has a fixed capacity. Any amount of fixed capacity storage can be emulated by multiplying your states: your new states become $\langle q, v \rangle$ where $q$ is an old state and $v$ a value stored in the register. So a "TM with a register" is not a TM, but trivially equivalent to a normal TM, and I ...

8

Yes a TM also has states. Formally, one can define TMs as $(Q, \Sigma, \Gamma, \square, \delta, q_0, \bar{q})$ with states $Q$, input alphabet $\Sigma$ not including the blank symbol $\square$, tape alphabet $\Gamma$, transition function $\delta$, initial state $q_0$ and terminal state $\bar{q}$. It might be differently defined but essentially it is all the ...

2

In order to decide whether a context-free grammar generates the empty language or not, you can compute the set of productive nonterminals. A nonterminal $A$ is productive if there is a rule $A \to \alpha$ where all nonterminals in $\alpha$ are already known to be productive. The set of productive nonterminals can be computed iteratively using the definition. ...

2

What about $\Sigma^*$ and $\Sigma^*\setminus\{11\}$?

2

Let $h\colon \Sigma \to \Sigma^*$ be the homomorphism given by $h(\sigma) = \sigma\sigma$. Then $L’ = h^{-1}(L)$. Now use the well-known fact that regular languages are closed under inverse homomorphism. Equivalently, start with a DFA for $L$, and modify the transition function so that whenever the new DFA reads a symbol $\sigma$, it simulates the old DFA ...

1

You can recognize $\{a^nb^n\}$ with just a counter (which is incremented by an $a$ and decremented by a $b$). No additional stack is needed. (If you used a stack, it would only contain $a$s; in general a counter is functionally equivalent to a stack whose alphabet consists of only one symbol.) The answer to the question you link to provides an example of a ...

1

The set $\Sigma^*$ consists of all words over $\Sigma$. A language over $\Sigma$ is not a word over $\Sigma$. Hence no language is a member of $\Sigma^*$, and no set of languages is a subset of $\Sigma^*$.

1

There will be no contradiction, since $D$ doesn't run in time $n^{1.4}$. In fact, what the proof of the time hierarchy theorem shows is that no equivalent Turing machine can run in time $n^{1.4}$, precisely because this will result in a contradiction. In other words, the language computed by $D$ lies outside of $\mathrm{DTIME}(n^{1.4})$. On the other hand, $... 1 Here is one possible way: $$\{ w \in \{0,1\}^* : \text{the number of 0s in w is congruent to 1 modulo 3, and the number of 1s is even} \}$$ 1 A Turing machine is fixed in size. Just as a piece of code doesn't increase in size when given bigger inputs, also a TM doesn't. The$TM\$ has to be defined beforehand, and its description should not depend on the particular specific input that was given to it.

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