logo
  • Home
  • Test & Rank
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Mining
  • Marine
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Jobs
  • Contact

Automata Theory Multiple Choice Questions | MCQs | Quiz

Automata Theory Interview Questions and Answers
Practice Automata Theory questions and answers for interviews, campus placements, online tests, aptitude tests, quizzes and competitive exams.

Get Started

•   Finite Automata Introduction
•   Moore Machine
•   Mealy Machine - 1
•   Mealy Machine - 2
•   Finite Automata Definitions
•   DFA Processing Strings
•   Simpler Notations
•   DFA Language
•   Finite Automata
•   Non Deterministic Automata
•   Transition Function
•   NFA Language
•   NFA & DFA Equivalence
•   DFA Applications
•   NFA Applications
•   Epsilon Transition
•   Epsilon Transitions Uses
•   Epsilon Closures
•   Union & Intersection
•   Regular Expression basics
•   Regular Operators
•   Regular Expressions
•   DFA Regular Expressions
•   States Conversion
•   Regular Language - 1
•   Regular Language - 2
•   Expressions-Automata
•   UNIX Regular Expression
•   Lexical Analysis
•   Text Patterns
•   Non Regular Languages
•   Pumping Lemma
•   Lemma Applications
•   Closure Properties
•   Reversal Homomorphism
•   Conversions
•   Emptiness Testing
•   Free Grammar Derivations
•   Inferences & Ambiguity
•   Sentential Forms
•   Parse Tree Construction
•   Trees Inference & Derivation
•   Parsers Applications
•   YACC Parser Generator
•   Markup Languages
•   Ambiguous Grammar
•   State PDA-Acceptance
•   Stack PDA-Acceptance
•   Push Down Automata
•   PDA - Grammars
•   Deterministic PDA
•   Regular Language & DPDA
•   DPDA & Free Languages
•   DPDA & Ambiguous
•   CFG Useless Symbols
•   Epsilon Productions
•   Eliminating Unit Production
•   Chomsky Normal Form
•   Context Free Language
•   CFL-Closure Properties
•   CFL-Other Normal Forms
•   Intersections
•   Transition Diagrams
•   Turing Machine Language-1
•   Turing Machine Language-2
•   Turing Machine & Halting
•   Programming Techniques
•   Multitape Turing Machines
•   One-Tape & Multitape TM's
•   Non Deterministic TM's
•   Multistack Machines
•   Turing Machine Simulation
•   Diagonalization Languages
•   Undecidability
•   Rice's Theorem & PCP
•   Polynomial Time Problems
•   Polynomial Time
•   Hamilton Circuit Problem
•   PSPACE
•   Randomized Algorithm
•   RP & ZPP Complexity

Best Reference Books

Automata Theory Books

« Prev Page
Next Page »

Automata Theory Questions and Answers – Multistack Machines, Counter Machines

Posted on May 17, 2017 by Manish

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.
advertisement

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.

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 these
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.
advertisement

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.

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: true
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.

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:
automata-theory-questions-answers-multistack-machines-counter-machines-q10

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.

« Prev Page - Automata Theory Questions and Answers – Non Deterministic Turing Machines
» Next Page - Automata Theory Questions and Answers – Simulation of Turing Machine

« Automata Theory Questions and Answers – Non Deterministic Turing Machines
Automata Theory Questions and Answers – Simulation of Turing Machine »
advertisement

Deep Dive @ Sanfoundry:

  1. Network Theory Questions and Answers
  2. C# Programming Examples on Data Structures
  3. Ruby Programming Questions and Answers
  4. Machine Tools & Machining Questions and Answers
  5. C Programming Examples on Linked List
  6. Electromagnetic Theory Questions and Answers
  7. C Programming Examples on Stacks & Queues
  8. Electrical Machines Questions and Answers
  9. Automata Theory Questions and Answers
  10. Automata Theory Questions and Answers – From Grammars to Push Down Automata
Manish Bhojasia
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Facebook | Twitter

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
Terms
Privacy Policy
Jobs
Bangalore Training
Online Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry. All Rights Reserved.