MCQ Computer Science

# Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-23

1. A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.
a) worst case
b) best case
c) average case
d) none of the mentioned

Explanation: A randomized algorithm is an algorithm that employs a degree of randomness as a part of its logic using random bits as inputs and in hope of producing average case good performace.

2. PSPACE is strictly the super set of:
a) Regular language
b) Context free language
c) Context Sensitive Language
d) None of the mentioned

Explanation: Membership of a string in a language defined by an arbitrary context sensitive grammar, or by an arbitrary determinisic context sensitive grammar, is a PSPACE -complete problem.

3. Which of the following cannot be solved using polynomial time?
a) Linear Programming
b) Greatest common divisor
c) Maximum matching
d) None of the mentioned

Explanation: In graph theory, a matching or independent edge set in a graph G is a set of edges without common vertices. Given a graph (V, E), a matching M in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.

4. Rec-DFA = { | M is a DFA and M recognizes input w}.
Fill in the blank:
Rec-DFA is ___________
a) Undecidable
b) Decidable
c) Non finite
d) None of the mentioned

Explanation: Under decidablity of regular language properties we have the following lemma which states that A DFA which recognizes an input w is decidable.

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

Explanation: Except Recursion, all the other options are techniques of Turing Machine construction which further includes, Checking off symbols and Storage in finite control.

a) one
b) two
c) n
d) infinite

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 is false for Quantum Turing machine?
a) Abstract machine
b) Any quantum algorithm can be expressed formally as a particular quantum turing machine
c) Gives a solution to ‘Is a universal quantum computer sufficient’
d) None of the mentioned

Explanation: ‘Is a universal quantum computer sufficient’ is one of the unsolved problem from physics.

8. State true or false:
Statement: Two track turing machine is equivalent to a standard turing machine.
a) true
b) false

Explanation: This can be generalized for n- tracks and can be proved equivalent using ennumerable languages.
9. RASP stands for:
a) Random access storage program
b) Random access stored program
c) Randomly accessed stored program
d) Random access storage programming

Explanation: RASP or Random access stored program is an abstract machine that has instances like modern stored computers.

10. A Language L may not be accepted by a Turing Machine if:
a) It it is recursively ennumerable
b) It is recursive
c) L can be ennumerated by some turing machine
d) None of the mentioned

Explanation: A language L is recursively ennumerable if and only if it can be ennumerated by some turing machine. A recursive ennumerable language may or may not be recursive.

11. A turing machine is a
a) real machine
b) abstract machine
c) hypothetical machine
d) more than one option is correct

Explanation: A turing machine is abstract or hypothetical machine thought by mathematician Alan Turing in 1936 capable of simulating any algorithm, however complicated it is.

12. A turing machine operates over:
a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned

Explanation: The turing machine operates on an infinite memory tape divided into cells. The machine positions its head over the cell and reads the symbol.

13. Which of the following a turing machine does not consist of?
a) input tape
c) state register
d) none of the mentioned

Explanation: A state register is one which stores the state of the turing machine, one of the finitely many. Among these is the special start state with which the state register is initialized.

14. Which of the following is not context free?
a) {w: nA=nB=nC}
b) {a*b*c*}
c) {a100b100}
d) All of the mentioned

Explanation: {a*b*c*} and (c) are regular languages while option (a) is not context free language.

15. Which of the following grammars is similar to Floyd Normal form?
a) Backus Naur Form
b) Kuroda Normal Form
c) Greibach Normal Form
d) Chomsky Normal Form