Automata Theory Multiple Choice Questions on “Turing Machine and Halting”.
1. The machine accept the string by entering into hA or it can:
a) explicitly reject x by entering into hR
b) enter into an infinte loop
c) Both (a) and (b)
d) None of the mentioned
Answer: c
Clarification: Three things can occur when a string is tested over a turing machine:
a) enter into accept halting state
b) enter into reject halting state
c) goes into loop forever
2. Which of the following can accept even palindrome over {a,b}
a) Push down Automata
b) Turing machine
c) NDFA
d) All of the mentioned
Answer: c
Clarification: A language generating strings which are palindrome is not regular, thus cannot b represented using a finite automaton.
3. Which of the functions can a turing machine not perform?
a) Copying a string
b) Deleting a symbol
c) Accepting a pal
d) Inserting a symbol
Answer: d
Clarification: Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.
4. If T1 and T2 are two turing machines. The composite can be represented using the expression:
a) T1T2
b) T1 U T2
c) T1 X T2
d) None of the mentioned
Answer: a
Clarification: If T1 and T2 are TMs, with disjoint sets of non halting states and transition function d1 and d2, respectively, we write T1T2 to denote this composite TM.