Automata Theory Multiple Choice Question & Answers (MCQs) set-8

1. The class of recursively ennumerable language is known as:
a) Turing Class
b) Recursive Languages
c) Universal Languages
d) RE

2. A multitape turing machine is ________ powerful than a single tape turing machine.
a) more
b) less
c) equal
d) none of the mentioned

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

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
5. Linear Bounded Automaton is a:
a) Finite Automaton
b) Turing Machine
c) Push down Automaton
d) None of the mentioned

6. State true or false:
Statement: Inorder to show something is Turing complete, it is enough to demonstrate that it can be used to simulate some Turing complete system.
a) true
b) false

7.Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}
a) A concrete undecidable problem
b) A is recognizable but not decidable
c) -A is not recognizable
d) All of the mentioned
8. Which of the following are correct statements?
a) TMs that always halt are known as Decidable problems
b) TMs that are guaranteed to halt only on acceptance are recursive ennumerable.
c) Both (a) and (b)
d) None of the mentioned
9. An algorithm is called efficient if it runs in ____________ time on a serial computer.
a) polynomial
b) non polynomial
c) logarithmic
d) none of the mentioned
10. Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?
a) C is undecidable if C is reducible to B
b) C is undecidable if B is reducible to C
c) C is decidable if A is reducible to C
d) C is decidable if C is reducible to B’s complement.

11. Which of the following options are correct with reference to P-complete problems?
a) used for the problems which are difficult to solve in limited space
b) every problem in P can be reduced to it using proper reductions
c) complete problem for complexity class P
d) all of the mentioned

12. Travelling sales man problem belongs to which of the class?
a) P
b) NP
c) Linear
d) None of the mentioned

13. Which of the following problems were reduced to Knapsack?
a) Exact Cover
b) Max Cut
c) 0-1 integer programming
d) None of the mentioned
14. The class PSPACE is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
d) All of the mentioned
15. Which of the following can be referred to as applications of Randomized algorithm?
a) Quicksort
b) Min Cut
c) Verifying Matrix Multiplication
d) All of the mentioned