Turing Machine

Which one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L \subseteq\{0,1\}$.

For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages. L 1 = {(M) | M takes more than 2021 steps on all inputs} L 2 = {(M) | M takes more than...

Which of the following languages are undecidable? Note that $$\langle M\rangle $$ indicates encoding of the Turing machine M. L 1 = $$\left\{ {\langle M\rangle |L\left( M \right) =...

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine...

Consider the following languages. $$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_1} = \left\{ {\left\langle M \right\rangle |M} \right.$$ takes at least $$2016$$ steps on some input $$\left. \,...

Which of the following decision problems are undecidable? $$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},$$ is $$L\left( {{N_1}} \right)...

Let $$ < M > $$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.} $$ Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machin...

Which of the following is/are undecidable? $$1.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \Phi ?$$ $$2.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \sum {{}^ * } ?$$ $$3.$$...

Consider the languages $${L_1}$$, $${L_2}$$ and $${L_3}$$ are given below. $$$\eqalign{ & {L_1} = \left\{ {{0^p}{1^q}\left| {p,q \in N} \right.} \right\} \cr & {L_2} = \left\{ {{0^...

Consider the following problem $$X.$$ Given a Turing machine $$M$$ over the input alphabet $$\sum , $$ any state $$q$$ of $$M$$ And a word $$w\,\,\varepsilon \,\,\sum {^ * ,} $$ do...

Regarding the power of recognition of languages, which of the following statement is false?

In which of the cases stated below is the following statement true? “For every non-deterministic machine $${M_1}$$ there exists an equivalent deterministic machine $${M_2}$$ recogn...

State whether the following statement is TRUE / FALSE. The problem is to whether a Turing Machine M accepts input $$w$$ is un-decidable.

State whether the following statement is TRUE / FALSE. A is recursive if both a and its complement are accepted by Turing Machine M accepts.