Automata Theory Questions and Answers – Equivalence of One-Tape and Multitape TM’s

«
»

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Equivalence of One-Tape and Multitape TM’s”.

1. Which of the following are related to construction of One Tape turing machines?
a) JFLAP
b) NFLAP
c) All of the mm
d) None of the mentioned
View Answer

Answer: a
Explanation: JFLAP is educational software written in java to experiment with the topics in automata theory and area of formal languages.
advertisement

2. Which of the following topics cannot be covered using JFLAPS?
a) L-System
b) Unrestricted Grammar
c) Regular Expression
d) None of the mentioned
View Answer

Answer: d
Explanation: Topics like regular expressions, context free languages and unrestricted grammar including parsers like LL,SLR parsers can be covered using JFLAPS.

3. State true or false:
Statement: Multitape turing machine have multi tapes where each tape is accessed with one head.
a) true
b) false
View Answer

Answer: b
Explanation: Multitape turing machines do have multiple tapes but they they are accessed by separate heads.
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

4. Which of the following statements is/are true?
a) Every multitape turing machine has its equivalent single tape turing machine
b) Every multitape turing machine is not an abstract machine
c) All of the mentioned
d) None of the mentioned
View Answer

Answer: a
Explanation: A multitape turing machine is an ordinary turing machine which is always abstract.And they do have their equivalent single tape turing machines.

5. Are Multitape and Multitrack turing machines same?
a) Yes
b) No
c) Somewhat yes
d) Cannot tell
View Answer

Answer: a
Explanation: Multitrack turing machines are special types of Multitape turing machines. In a standard n-tape Turing machine, n heads move independently along n-tracks.
advertisement

6. In a n-track turing machine, _________ head/heads read and write on all tracks simultaneously.
a) one
b) two
c) n
d) infinite
View Answer

Answer: a
Explanation: In a n-track Turing machine, one head reads and writes on all tracks simultaneously. A tape position in a n-track Turing Machine contains n symbols from the tape alphabet.

7. Which of the following does not exists?
a) Turing Machine with Multiple heads
b) Turing Machine with infinite tapes
c) Turing machine with two dimensional tapes
d) None of the mentioned
View Answer

Answer: d
Explanation: All of the mentioned are one or the other kind of Turing machines in existence.
advertisement

8. Can a multitape turing machine have an infinte number of tapes?
a) Yes
b) No
View Answer

Answer: b
Explanation: One needs a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.

9. Every language accepted by a k-tape TM is _____ by a single-tape TM.
a) accepted
b) not accepted
c) generated
d) not generated
View Answer

Answer: a
Explanation: Its the theorem that states Every multitape turing machine can be simulated by a single tape turing machine and the corresponding language can be accepted.
advertisement

10. Which of the following is/are a basic TM equivalent to?
a) Multitrack TM
b) Multitape TM
c) Non-deterministic TM
d) All of the mentioned
View Answer

Answer: d
Explanation: Tms can be used as both: language recognizers/Computers. TMs are like universal computing machines with universal storage.

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.

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.