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
View Answer
Explanation: Turing machine is known as universal computer. It is denoted by M=(Q,S,? ,d ,q0, B,F)
a) Halting problem
b) Boolean Satisfiability problem
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: Alan turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
a) 9
b) 11
c) 12
d) 15
View Answer
Explanation: None.
a) cooperative behaviour
b) graph theory
c) Both (a) and (b)
d) None of the mentioned
View Answer
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.
a) decidable decision problem
b) undecidable decision problem
c) not a decision problem
d) none of the mentioned
View Answer
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.
a) NP, P
b) NP, NP hard
c) P, P complete
d) None of the mentioned
View Answer
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
View Answer
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
View Answer
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
View Answer
Explanation: The complement of all the problems in PSPACE are also in PSPACE, meaning co-PSPACE= PSPACE.
a) tractable
b) intractable
c) computational
d) none of the mentioned
View Answer
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
View Answer
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
View Answer
Explanation: Every context sensitive grammar which does not produce an empty string can be generated by a grammar in Kuroda Normal form.
|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
View Answer
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).
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) None of the mentioned
View Answer
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
View Answer
Explanation: The format says: If A->B is a production, B is called A-derivable.Thus A to be A-derivable, a production : A-> A need to exist.
