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.

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

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