Automata Theory Questions and Answers – Non Deterministic Turing Machines

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Non Deterministic Turing Machines”.

1. X is a simple mathematical model of a computer. X has unrestricted and unlimited memory. X is a FA with R/W head. X can have an infinite tape divided into cells, each cell holding one symbol.
Name X?
a) Push Down Automata
b) Non deterministic Finite Automata
c) Turing machines
d) None of the mentioned
View Answer

Answer: c
Explanation: Turing machine is known as universal computer. It is denoted by M=(Q,Σ,Ґ ,δ ,q0, B,F)

2. Which of the following is/are not an application of turing machine?
a) Language Recognization
b) Computers of functions on non negative numbers
c) Generating devices
d) None of the mentioned
View Answer

Answer: d
Explanation: A turing machine can have many applications like : Enumerator (A turing machine with an output printer), function computer, etc.

3. State true or false:
Statement: Turing Machine can change symbols on its tape, whereas the FA cannot change symbols on tape.
a) true
b) false
View Answer

Answer: a
Explanation: The following mentioned is the difference between 2-way FA and TM. Another instance is that TM has a read/write tape head while FA doesn’t.
advertisement
advertisement

4. Which of the following cannot be a possibility of a TM while it processes an input?
a) Enters accepting state
b) Enters non-accepting state
c) Enters infinite loop and never halts
d) None of the mentioned
View Answer

Answer: d
Explanation: The following mentioned are the only possibilities of operating a string through a turing machine.

5. Pick the odd one out.
a) Subroutines
b) Multiple tracks
c) Shifting over
d) Recursion
View Answer

Answer: d
Explanation: Except Recursion, all the other options are techniques of Turing Machine construction which further includes, Checking off symbols and Storage in finite control.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Which among the following is not true for 2-way infinte TM?
a) tape in both directions
b) Leftmost square not distinguished
c) Any computation that can be performed by 2-way infinite tape can also be performed by standard TM.
d) None of the mentioned
View Answer

Answer: d
Explanation: All of the mentioned are correct statements for a two way infinite tape turing machine. Theorems say the power of such a machine is in no way superior than a standard turing machine.

7. Can a turing machine act like a transducer?
a) yes
b) no
View Answer

Answer: a
Explanation: A turing machine can be used as a transducer. The most obvious way to do this is to treat the entire non blank portion of the initial tape as input, and to treat the entire blank portion of the tape when the machine halts as output.
advertisement

8. Which of the following does not exists?
a) Mutitape TM
b) Multihead TM
c) Multidimentional TM
d) None of the mentioned
View Answer

Answer: d
Explanation: If the tape contains k-dimentional array of cells infinte in all 2k directions, for some fixed k and has a finite control, the machine can be called Multidimentional TM.

9. Enumerator is a turing machine with __________
a) an output printer
b) 5 input tapes
c) a stack
d) none of the mentioned
View Answer

Answer: a
Explanation: Here, the turing machine can use the printer as an output device to print strings.
Note: There is no input to an enumerator. If it doesn’t halt, it may print an infinite set of strings.
advertisement

10. For the following language, an enumerator will print:
L={anbn|n>=0}
a) anbn
b) {ab, a2b2, a3b3, …}
c) {e, ab, a2b2, a3b3, …}
d) None of the mentioned
View Answer

Answer: b
Explanation: An enumerator is a turing machine with an output printer. It can use an printer as an output device to print output strings. As n also holds the value , epsilon will also be a part of the output set.

11. Complete the following statement:
Statement : A language is turing recognizable if an only if ___________
a) an enumerator enumerates it
b) it is finite
c) all of the mentioned
d) none of the mentioned
View Answer

Answer: a
Explanation: If an Enumerator E enumerates a language L, there is a turing machine M that recognizes language L. Also, If a turing machine M recognizes a language L, there is an enumerator for L.

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.