Automata Theory Questions and Answers – Turing Machine-Notation and Transition Diagrams

«
»

This set of Automata Theory Interview Questions and Answers for freshers focuses on “Turing Machine – Notation and Transition Diagrams”.

1. A turing machine is a
a) real machine
b) abstract machine
c) hypothetical machine
d) more than one option is correct
View Answer

Answer: d
Explanation: A turing machine is abstract or hypothetical machine thought by mathematician Alan Turing in 1936 capable of simulating any algorithm, however complicated it is.
advertisement

2. A turing machine operates over:
a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned
View Answer

Answer: b
Explanation: The turing machine operates on an infinite memory tape divided into cells. The machine positions its head over the cell and reads the symbol.

3. Which of the functions are not performed by the turing machine after reading a symbol?
a) writes the symbol
b) moves the tape one cell left/right
c) proceeds with next instruction or halts
d) none of the mentioned
View Answer

Answer: d
Explanation: After the read head reads the symbol from the input tape, it performs the following functions:
a) writes a symbol(some model allow symbol erasure/no writing)
b) moves the tape left or right (some models allows no motion)
c) proceeds with subsequent instruction or goes either into accepting halting state or rejecting halting state.
advertisement
advertisement

4. ‘a’ in a-machine is :
a) Alan
b) arbitrary
c) automatic
d) None of the mentioned
View Answer

Answer: c
Explanation: The turing machine was invented by Alan turing in 1936. He named it as a-machine(automatic machine).

5. Which of the problems were not answered when the turing machine was invented?
a) Does a machine exists that can determine whether any arbitrary machine on its tape is circular.
b) Does a machine exists that can determine whether any arbitrary machine on its tape is ever prints a symbol
c) Hilbert Entscheidungs problem
d) None of the mentioned
View Answer

Answer: d
Explanation: Invention of turing machine answered a lot of questions which included problems like decision problem, etc.) . Alan was able to prove the properties of computation using such model.
advertisement

6. The ability for a system of instructions to simulate a Turing Machine is called _________
a) Turing Completeness
b) Simulation
c) Turing Halting
d) None of the mentioned
View Answer

Answer: a
Explanation: Turing Completeness the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete.

7. Turing machine can be represented using the following tools:
a) Transition graph
b) Transition table
c) Queue and Input tape
d) All of the mentioned
View Answer

Answer: d
Explanation: We can represent a turing machine, graphically, tabularly and diagramatically.
advertisement

8. Which of the following is false for an abstract machine?
a) Turing machine
b) theoretical model of computer
c) assumes a discrete time paradigm
d) all of the mentioned
View Answer

Answer: d
Explanation: A n abstract machine also known as abstract computer, is a theoretical model of computer or hardware system in automata theory. Abstraction in computing process usually assumes a discrete time paradigm.

9. Fill in the blank with the most appropriate option.
Statement: In theory of computation, abstract machines are often used in ___________ regarding computability or to analyze the complexity of an algorithm.
a) thought experiments
b) principle
c) hypothesis
d) all of the mentioned
View Answer

Answer: d
Explanation: A thought experiment considers some hypothesis, theory or principle for the purpose of thinking through its consequences.
advertisement

10. State true or false:
Statement: RAM model allows random access to indexed memory locations.
a) true
b) false
View Answer

Answer: a
Explanation: In computer science, Random access machine is an abstract machine in the general class of register machines. Random access machine should not be confused with Random access memory.

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

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 & technical discussions at Telegram SanfoundryClasses.