Recent questions tagged turing-machine

Let $M$ be a deterministic Turing machine. During a computation on input $w$, suppose $M$ enters exactly the same complete configuration at two different times before rea...

A deterministic Turing machine starts on a blank tape.Which of the following gives an example of a computation that runs forever without ever repeating exactly the same c...

Suppose $M$ recognizes a Turing-recognizable language $A$.Which statement is necessarily true?There must exist some $w\notin A$ on which $M$ loops forever. $M$ must loop ...

Let $L$ be any Turing-recognizable language.Which of the following is always possible?Construct a TM that accepts every $w\in L$ and loops forever on every $w\notin L$, n...

Consider the following deterministic Turing machine $M$ with input alphabet $\Sigma=\{a,b\}$What is $L(M)$?$\{w\in\{a,b\}^*\mid w\text{ ends in }a\}$ $\{w\in\{a,b\}^*\mid...

Let $M$ be a Turing machine that recognizes language $L$, and suppose $w\notin L.$Which of the following behaviors are possible when $M$ is run on $w$?$M$ accepts $w$. $M...

Consider the following TM strategy for $L=\{b^ic^i\mid i\ge0\}.$It repeatedly:changes the leftmost unmatched $b$ to $\sqcup$ (blank symbol)$,$ scans right to the end of t...

Consider $L=\{0^n1^n2^n\mid n\ge0\}.$Which of the following gives a correct high-level strategy for a single-tape Turing machine recognizing $L$?Repeatedly mark the leftm...

Suppose a Turing machine makes the following one-step move:$$011q_7\,00101 \;\vdash\; 0110q_7\,0101.$$What transition must have been used, and what is the next configurat...

Consider a deterministic single-tape Turing machine$$M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\text{accept}},q_{\text{reject}}).$$Which of the following are required in the stand...

The language is $L=\{a.b^n \;or\; b.a^n | n>0\}$ where $\sum = \{a,b\}$

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

 

Which of the following represents the output of the transition function( $\delta$ )$ \begin{array}{l} \delta\left(q_{0}, a\right)=\left(q_{1}, x, R\right) \\\delta\left(...

Question:LetL = { a^i b^j / i != 2j+1 } where i,j >=1  (a) Is LLL a deterministic context-free language (DCFL)?(b) Justify your answer with reasoning.

Consider the following languages:$L_{1}$ is the set of languages recognised by a deterministic pushdown automaton.$L_{2}$ is the set of languages recognised by a nondeter...

The complexity class $\textsf{NP}$ corresponds to the class of languages which can be accepted by some nondeterministic Turing machine in polynomial time.The complexity c...