Automata Theory Questions and Answers – Multistack Machines, Counter Machines

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Multistack Machines, Counter Machines”.

1. Can a single tape turing machine be simulated using deterministic 2-stack turing machine?
a) Yes
b) No
c) Cannot be said
d) none of the mentioned
View Answer

Answer: a
Explanation: The symbols to left of the head of turing macine being simulated can be stored on the stack while the symbols on the right of the head can be placed on another stack. On each stack, symbols closer to the TM’s head are placed closer to the top of the stack than symbols farther from the TM’s head.

2. A ___________ is a multi tape turing machine whose input tape is read only.
a) Counter Machine
b) Multi-stack
c) Alternating Turing machine
d) None of the mentioned
View Answer

Answer: a
Explanation: Counter machines are offline(a multitape turing machine whose input is read only) whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a blank symbol B.

3. Instantaneous description of a counter machine can be described using:
a) the input tape contents
b) position of the input head
c) distance of storage heads from symbol Z
d) all of the mentioned
View Answer

Answer: d
Explanation: Instantaneous description of a counter machine can be described by the state, the input tape contents, the position of input head, and the distance of storage heads from the symbol Z. The counter machine can really store a count on each tape and tell if the count is zero.
advertisement
advertisement

4. Which of the following parameters cannot be used to restrict a turing machine?
a) tape alphabets
b) number of tapes
c) number of states
d) none of the mentioned
View Answer

Answer: d
Explanation: Another procedure to restrict a turing machine is to limit the size of tape alphabet or reduce the number of states. If the tape alphabets, number of tapes or number of states are limited, then there is only a finite number of different turing machine, so the restricted model is more powerful than the original one.

5. Linear Bounded Automaton is a:
a) Finite Automaton
b) Turing Machine
c) Push down Automaton
d) None of the mentioned
View Answer

Answer: b
Explanation: Linear Bounded Automaton is a type of Turing Machine where tape is not allowed to move off the portion of the tape containing the input. It is a Turing machine with limited amount of memory.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. State true or false:
Statement: Using a two track tape, we can use a semi infinite tape to simulate an infinte tape.
a) true
b) false
View Answer

Answer: a
Explanation: A TM with a semi-infinite tape means that there are no cells to the left of the initial head position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track tape.

7. Which of the following is true with reference to semi-infinite tape using a two track tape?
a) Can simulate a two way tape
b) Upper track represents the head-right cells
c) Lower track represents the head-left cells
d) All of the mentioned
View Answer

Answer: d
Explanation: The upper track represents the cells of the original TM that are at the right of the initial head position. The lower track represents the cells to the left of the initial head position, but in reverse order.
advertisement

8. Which among the following options are correct?
Statement 1: TMs can accept languages that are not accepted by any PDA with one stack.
Statement 2: But PDA with two stacks can accept any language that a TM can accept.
a) Statement 1 and 2, both are correct
b) Statement 1 is correct but Statement 2 is false
c) Statement 2 is correct while Statement 1 is false
d) Statement 1 and 2, both are false
View Answer

Answer: a
Explanation: Both the statements are true. Both the statements are properties of Multistack machines.

9. A two-way infinite tape turing machine is ________ superior than the basic model of the turing machine in terms of power.
a) more
b) less
c) no way
d) none of the mentioned
View Answer

Answer: c
Explanation: A two way infinite tape turing machine is a turing machine with its input tape infinte in both directions, the other component being the same as the basic model.
advertisement

10. For a basic turing machine, there exists an equivalent :
a) 2-counter machine
b) 3-counter machine
c) 4-counter machine
d) All of the mentioned
View Answer

Answer: d
Explanation: For a basic TM, there exists a 2-counter, 3-counter and 4-counter machines
We can prove them using Deterministic two stack turing machine.
Counter machine:
The two stack turing counter machine diagram

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