(51) S -> a α b I b a c I ab
S -> α S I b
S -> α bb I ab
S -> bdb I b
The grammar described above is
(A) Context free
(B) Context sensitive
(C) Regular
(D) LR(k)
ANSWER: Context sensitive
(52) Match the following
a. Regular expression I. Syntax analysis
b. Pushdown automata II Code generation
c. Dataflow analysis III Lexical analysis
d. Register allocation IV Code optimization
(A) a – III, b – IV, c – I, d – II
(B) a – IV, b – III, c – I, d – II
(C) a – III, b – I, c – IV, d – II
(D) a – II, b – III, c – IV, d – I
ANSWER: a – III, b – I, c – IV, d – II
(53) Which of the following statement is false for a turing machine?
(A) There exists an equivalent deterministic turing machine for every non-deterministic turing machine
(B) Turing decidable languages are closed under intersection and complementation
(C) Turing recognizable languages are closed under union and intersection
(D) Turing recognizable languages are closed under union and complementation
ANSWER: Turing recognizable languages are closed under union and complementation
(54) The problem, which is not NP-hard, is
(A) Finding bi-connected problem of a graph
(B) The graph colouring problem
(C) Hamiltonian circuit problem
(D) The 0/1 Knapsack problem
ANSWER: Hamiltonian circuit problem
(55) If P≠NP the statement which holds true is
(A) NP-hard = NP
(B) NP-complete ∩ P = Φ
(C) P=NP-complete
(D) NP-complete=NP
ANSWER: NP-complete ∩ P = Φ