Automata Theory Questions and Answers – The Language of Turing Machine

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The Language of Turing Machine”.

1. A turing machine that is able to simulate other turing machines:
a) Nested Turing machines
b) Universal Turing machine
c) Counter machine
d) None of the mentioned
View Answer

Answer: b
Explanation: A more mathematically oriented definition with the same universal nature was introduced by church and turing together called the Church-Turing thesis(formal theory of computation).

2. Which of the problems are unsolvable?
a) Halting problem
b) Boolean Satisfiability problem
c) Halting problem & Boolean Satisfiability problem
d) None of the mentioned
View Answer

Answer: c
Explanation: Alan turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

3. Which of the following a turing machine does not consist of?
a) input tape
b) head
c) state register
d) none of the mentioned
View Answer

Answer: d
Explanation: A state register is one which stores the state of the turing machine, one of the finitely many. Among these is the special start state with which the state register is initialized.
advertisement
advertisement

4. The value of n if turing machine is defined using n-tuples:
a) 6
b) 7
c) 8
d) 5
View Answer

Answer: b
Explanation:
The 7-tuple definition of turing machine: (Q, S, G, d, q0, B, F)
where Q= The finite set of states of finite control
S= The finite set of input symbols
G= The complete set of tape symbols
d= The transition function
q0= The start state, a member of Q, in which the finite control is found initially.
B= The blank symbol
F= The set of final or accepting states, a subset of Q.

5. If d is not defined on the current state and the current tape symbol, then the machine ______
a) does not halts
b) halts
c) goes into loop forever
d) none of the mentioned
View Answer

Answer: b
Explanation: If we reach hA or hR, we say TM halts. Once it has halted, it cannot move further, since d is not defined at any pair (hA,X) or (hR,X) where hA = accept halting state and hR = reject halting state.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Statement: Instantaneous descriptions can be designed for a Turing machine.
State true or false:
a) true
b) false
View Answer

Answer: a
Explanation: Inorder to describe formally what a Turing machine does, we need to develop a notation for configurations or Instantaneous descriptions(ID).

7. Which of the following are the models equivalent to Turing machine?
a) Multi tape turing machine
b) Multi track turing machine
c) Register machine
d) All of the mentioned
View Answer

Answer: d
Explanation: Many machines that might be thought to have more computational capability than a simple UTM can be shown to have no more power. They might compute faster or use less memory but cannot compute more powerfully i.e. more mathematical questions.
advertisement

8. Which among the following is incorrect for o-machines?
a) Oracle Turing machines
b) Can be used to study decision problems
c) Visualizes Turing machine with a black box which is able to decide cerain decion problems in one operation
d) None of the mentioned
View Answer

Answer: d
Explanation: In automata theory, an o- machine or oracle machine is a abstract machine used to study decision problems. The problem the oracle solves can be of any complexity class. Even undecidable problems like halting problems can be used.

9. RASP stands for:
a) Random access storage program
b) Random access stored program
c) Randomly accessed stored program
d) Random access storage programming
View Answer

Answer: b
Explanation: RASP or Random access stored program is an abstract machine that has instances like modern stored computers.
advertisement

10. Which of the following is not true about RASP?
a) Binary search can be performed more quickly using RASP than a turing machine
b) Stores its program in memory external to its state machines instructions
c) Has infinite number of distinguishable, unbounded registers
d) Binary search can be performed less quickly using RASP than a turing machine
e) More than two options are incorrect
View Answer

Answer: d
Explanation: In theoretical computer science, the random access stored program( RASP ) machine model is an abstract machine used for the purpose of algorithm development and algorithm complexity theory.

11. State true or false:
Statement: RASP is to RAM like UTM is to turing machine.
a) true
b) false
View Answer

Answer: a
Explanation: The Rasp is a random access machine model that, unlike the RAM has its program in its registers together with its input. The registers are unbounded(infinite in capacity); whether the number of registers is finite is model-specific.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.