Turing Machines Questions and Answers

Q: Which one of the following statements is equivalent to the following assertion?Turing machine \(M\) decides the language \(L \subseteq \{0,1\}^{*}\)

The equivalent statement is M accepts all input strings in L and rejects all input strings in {0,1}* - L.A Turing machine decides L when it halts on every input, accepting exactly the strings of L and rejecting all the others. Both halves are needed.'Halts on all input strings' says nothing about which strings are accepted, so M could decide a different language. 'Accepts all input strings in L' is only recognition: M might accept other strings too, or loop forever on strings outside L. 'Rejects all strings outside L' is the mirror image and says nothing about the strings in L.

Q: Consider the TM described below for computing 2’s complement using a transition diagram. In this diagram few of the transition input entries are missing and are denoted by I, II and III.Here L represents left, R represents right and N represents Accept (No movement)Which of the following is exact replacement for I, II and III above in the order.

The missing entries are (0, 1, N), (B, 1, N), (1, 0, L).The two's complement of a binary number is its ones' complement plus 1. In state q0 the machine moves right inverting every bit, (0, 1, R) and (1, 0, R), which forms the ones' complement. At the blank after the number it turns back left into q1.In q1 it adds 1 starting from the rightmost bit. A 1 plus 1 gives 0 with a carry, so it writes 0 and keeps moving left: III = (1, 0, L). A 0 plus the carry gives 1 with no further carry, so it writes 1 and accepts: I = (0, 1, N). If the carry runs past the leftmost bit onto the blank, it writes 1 there and accepts: II = (B, 1, N).The other options either do not write the carry correctly or move right, away from the bits still to be processed.

Q: Which statement is true ?

The true statement is that the tape of a Turing machine is infinite.A Turing machine has an unbounded tape divided into cells, which can be extended without limit as the computation needs. This unlimited memory is what makes the Turing machine more powerful than finite automata and pushdown automata.The tape is not finite, and its size does not depend on whether the language is regular. A machine with a tape bounded by the input length is a different model, the linear bounded automaton.

Q: What is the language accepted by a Turing machine ?

A Turing machine accepts the recursively enumerable languages.The languages that some Turing machine accepts are exactly the recursively enumerable (Type 0) languages, the top of the Chomsky hierarchy. This class contains the context-sensitive, context-free and regular languages as subsets.Each of the other options adds 'only', which is what makes it wrong. A Turing machine can accept regular, context-free and context-sensitive languages, but its power goes beyond each of them.

Q: The order of transition functions can be taken from Turing Machine (TM) is

The key's answer is randomly.A Turing machine's transition function is a set of rules of the form δ(q, a) = (p, b, D). At each step the machine uses the one rule that matches its current state and the symbol under the head; the position of the rule in a written list plays no part. So the transition rules can be listed and taken in any order, which is what the paper means by randomly.'Sequentially' would mean the rules are applied in the order written, which is not how a Turing machine works, so it and the options built on it are wrong.

Which one of the following statements is equivalent to the following assertion?

Turing machine \(M\) decides the language \(L \subseteq \{0,1\}^{*}\)

A.Turing machine \(M\) halts on all input strings in \(\{0,1\}^{*}\)
B.Turing machine \(M\) accepts all input strings in \(L\)
C.Turing machine \(M\) rejects all input strings in \(\{0,1\}^{*} - L\)
D.Turing machine \(M\) accepts all input strings in \(L\) and rejects all input strings in \(\{0,1\}^{*} - L\)

Exam Year(s)

GATE CS - 2026,

Answer: D

The equivalent statement is M accepts all input strings in L and rejects all input strings in {0,1}* - L.

A Turing machine decides L when it halts on every input, accepting exactly the strings of L and rejecting all the others. Both halves are needed.

'Halts on all input strings' says nothing about which strings are accepted, so M could decide a different language. 'Accepts all input strings in L' is only recognition: M might accept other strings too, or loop forever on strings outside L. 'Rejects all strings outside L' is the mirror image and says nothing about the strings in L.

Discuss in Forum

Consider the TM described below for computing 2’s complement using a transition diagram. In this diagram few of the transition input entries are missing and are denoted by I, II and III.

Turing machine transition diagram: q0 with self-loops (0, 1, R) and (1, 0, R) goes to q1 on (B, B, L); q1 has a self-loop labelled III and two arrows labelled I and II to the accepting state q2

Here L represents left, R represents right and N represents Accept (No movement)

Which of the following is exact replacement for I, II and III above in the order.

A.(0, 1, N), (B, 1, N), (1, 0, L)
B.(0, 0, N), (B, 1, N), (1, 0, R)
C.(1, 0, N), (B, 0, N), (0, 1, R)
D.(1, 1, N), (B, 0, N), (0, 1, L)

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: A

The missing entries are (0, 1, N), (B, 1, N), (1, 0, L).

The two's complement of a binary number is its ones' complement plus 1. In state q0 the machine moves right inverting every bit, (0, 1, R) and (1, 0, R), which forms the ones' complement. At the blank after the number it turns back left into q1.

In q1 it adds 1 starting from the rightmost bit. A 1 plus 1 gives 0 with a carry, so it writes 0 and keeps moving left: III = (1, 0, L). A 0 plus the carry gives 1 with no further carry, so it writes 1 and accepts: I = (0, 1, N). If the carry runs past the leftmost bit onto the blank, it writes 1 there and accepts: II = (B, 1, N).

The other options either do not write the carry correctly or move right, away from the bits still to be processed.

Discuss in Forum

Which statement is true ?

A.The tape of turing machine is infinite.
B.The tape of turing machine is finite.
C.The tape of turing machine is infinite when the language is regular.
D.The tape of turing machine is finite when the language is non-regular.

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: A

The true statement is that the tape of a Turing machine is infinite.

A Turing machine has an unbounded tape divided into cells, which can be extended without limit as the computation needs. This unlimited memory is what makes the Turing machine more powerful than finite automata and pushdown automata.

The tape is not finite, and its size does not depend on whether the language is regular. A machine with a tape bounded by the input length is a different model, the linear bounded automaton.

Discuss in Forum

What is the language accepted by a Turing machine ?

A.Regular language only
B.Context-free language only
C.Context-sensitive language only
D.Recursively enumerable language

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: D

A Turing machine accepts the recursively enumerable languages.

The languages that some Turing machine accepts are exactly the recursively enumerable (Type 0) languages, the top of the Chomsky hierarchy. This class contains the context-sensitive, context-free and regular languages as subsets.

Each of the other options adds 'only', which is what makes it wrong. A Turing machine can accept regular, context-free and context-sensitive languages, but its power goes beyond each of them.

Discuss in Forum

The order of transition functions can be taken from Turing Machine (TM) is

A.randomly
B.sequentially
C.both (A) and (B)
D.Neither (A) nor (B)

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: A

The key's answer is randomly.

A Turing machine's transition function is a set of rules of the form δ(q, a) = (p, b, D). At each step the machine uses the one rule that matches its current state and the symbol under the head; the position of the rule in a written list plays no part. So the transition rules can be listed and taken in any order, which is what the paper means by randomly.

'Sequentially' would mean the rules are applied in the order written, which is not how a Turing machine works, so it and the options built on it are wrong.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Turing Machines Questions and Answers || Turing Machines MCQ Questions and Answers || Turing Machines GK Questions and Answers || Turing Machines GK MCQ Questions || Turing Machines Multiple Choice Questions and Answers || Turing Machines GK || GK on Turing Machines || Theory of Computation Questions and Answers || Theory of Computation MCQ Questions and Answers || Theory of Computation GK Questions and Answers || GK on Theory of Computation

Turing Machines Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications