Recent questions tagged turing-machine

There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself a...

L(M)={0}We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable)I don’t understand why th...

The state diagram for the initial part of this turing machine given as:Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' ...

Given below are two statements:Statement I: If $f$ and $g$ are two functions and $f=O(g)$ but $g \neq o(f)$, we say that the growth rate of $g$ is smaller than that of $f...

The set of turning machine codes for $\text{TM's}$ that accept all inputs that are palindromes (possible along with some other inputs) is decidableThe language of codes f...

Consider following statements:I. A context free language is generated by $\text{LR(o)}$ grammar if and only if it is accepted by a deterministic pushdown automata and has...

A Turing Machine for the language $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} \mathrm{c}^{\mathrm{n}} \mathrm{d}^{\mathrm{m}} \mid \mathrm{n} \geq ...

A Turing Machine for the language $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} \mathrm{c}^{\mathrm{n}} \mathrm{d}^{\mathrm{m}} \mid \mathrm{n} \geq ...

A Turing Machine for the language $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} \mathrm{c}^{\mathrm{n}} \mathrm{d}^{\mathrm{m}} \mid \mathrm{n} \geq ...

A Turing Machine for the language $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} \mathrm{c}^{\mathrm{n}} \mathrm{d}^{\mathrm{m}} \mid \mathrm{n} \geq ...

$\left(\left\{\mathrm{q}_{0}, \mathrm{q}_{1}, \mathrm{q}_{2}, \mathrm{q}_{3}, \mathrm{q}_{4}, \mathrm{q}_{5}, \mathrm{q}_{6}, \mathrm{q}_{7}, \mathrm{q}_{\mathrm{f}}\righ...

Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells f...

Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turi...

Let $L$ be the following language.$L=\left\{P\left(x_{1}, x_{2}, \ldots, x_{n}\right) \mid P\right.$ is a polynomial with an integral root $\}$.Explain why the following ...

Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turi...

Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turi...