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

1. X is a simple mathematical model of a computer. X has unrestricted and unlimited memory. X is a FA with R/W head. X can have an infinite tape divided into cells, each cell holding one symbol.
Name X?
a) Push Down Automata
b) Non deterministic Finite Automata
c) Turing machines
d) None of the mentioned

Explanation: Turing machine is known as universal computer. It is denoted by M=(Q,S,? ,d ,q0, B,F)

2. Which of the problems are unsolvable?
a) Halting problem
b) Boolean Satisfiability problem
c) Both (a) and (b)
d) None of the mentioned

Explanation: Alan turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

3. John is asked to make an automaton which accepts a given string for all the occurrence of ‘1001’ in it. How many number of transitions would John use such that, the string processing application works?
a) 9
b) 11
c) 12
d) 15

Explanation: None.

4. Prisonner’s dilemma can be related to the following:
a) cooperative behaviour
b) graph theory
c) Both (a) and (b)
d) None of the mentioned

Explanation: Prisonner’s dilemma is a standard example of a game analysed in game theory where rational cooperative behaviour is judged on the basis of rewards and punishment.

5. Post Correspondence problem is
a) decidable decision problem
b) undecidable decision problem
c) not a decision problem
d) none of the mentioned

Explanation: Post Correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Being simpler than halting problem, it can be used in proofs of undecidability.

6. A problem which is both _______ and _________ is said to be NP complete.
a) NP, P
b) NP, NP hard
c) P, P complete
d) None of the mentioned

Explanation: A problem is said to be NP Hard if an algorithm for solving the problem can be translated from for solving any other problem. It is easier to show a problem NP than showing it Np Hard.

7. A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.
a) 1
b) 2
c) 3
d) all of the mentioned

Explanation: A problem X belongs to P complexity class if there exist atleast 1 algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input. Thus, all the options are correct.

8. Which of the following cannot solve Hamilton Circuit problem?
a) DNA Computer
b) Monte Carlo algorithm
c) Dynamic programming
d) None of the mentioned

Explanation: Using Inclusion-exclusion principle, Andreas showed how to solve Hamilton Circuit problem in arbitrary n-vertex graphs by a Monte Carlo algorithm in time O(1.657n).

9. Complement of all the problems in PSPACE is ________
a) PSPACE
b) NL
c) P
d) All of the mentioned

Explanation: The complement of all the problems in PSPACE are also in PSPACE, meaning co-PSPACE= PSPACE.

10. A problem is called __________ if its has an efficient algorithm for itself.
a) tractable
b) intractable
c) computational
d) none of the mentioned

Explanation: A problem is called intractable iff there is an efficient (i.e. polynomial time) algorithm that solves it. A problem is called intractable iff there exists no efficient algorithm that solves it.

11. Which of the following is not a negative property of Context free languages?
a) Intersection
b) Complement
c) Both (a) and (b)
d) None of the mentioned

Explanation: Context free languages are not closed under complement and intersection. Thus, are called Negative properties.

12. Every Kuroda Normal form grammar generates ___________
a) Context free grammar
b) Context sensitive grammar
c) Unrestricted grammar
d) None of the mentioned

Explanation: Every context sensitive grammar which does not produce an empty string can be generated by a grammar in Kuroda Normal form.

13.Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying
|t|>=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy.
Let p be the number of variables in CNF form of the context free grammar. The value of n in terms of p :
a) 2p
b) 2p
c) 2p+1
d) p2

Explanation: This inequation has been derived from derivation tree for t which must have height at least p+2(It has more than 2p leaf nodes, and therefore its height is >p+1).

14. The format: A->aB refers to which of the following?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) None of the mentioned

Explanation: A context free grammar is in Greibach Normal Form if the right hand sides of all the production rules start with a terminal, optionally followed by some variables.

15. A can be A-> derivable if and only if __________
a) A-> A is actually a production
b) A->B, B-> A exists
c) Both (a) and (b)
d) None of the mentioned