 A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

 81. The language accepted by the nondeterministic pushdown automaton M= ({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) with transitions δ (q0 a, z) = { (q1 a), (q2 λ)}; δ (q1, b, a) = { (q1, b)} δ (q1, b, b) ={ (q1 b)}, δ (q1, a, b) = { (q2, λ)} is a. L(abb*a) b. {a} U L(abb*a) c. L(ab*a) d. {a} U L(ab*a)

 82. The language L = {a^n b^n a^m b^m | n ≥ 0, m ≥ 0} is a. Context free but not linear b. Context free and linear c. Not Context free and not linear d. Not Context free but linear

 83. Assume statements S1 and S2 defined as : S1 : L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2 : The set of all Turing machines is countable. Which of the following is true ? a. S1 is correct and S2 is not correct b. Both S1 and S2 are correct c. Both S1 and S2 are not correct d. S1 is not correct and S2 is correc

 84. Non-deterministic pushdown automaton that accepts the language generated by the grammar: S→aSS | ab is (A) δ(q0, λ, z) = { (q1, z)}; δ(q0, a, S) = { (q1, SS)}, (q1, B) } δ(q0, b, B) = { (q1, λ)}, δ(q1, λ, z) = { (qf, λ)} (B) δ(q0, λ, z) = { (q1, Sz)}; δ(q0, a, S) = { (q1, SS)}, (q1, B) } δ(q0, b, B) = { (q1, λ)}, δ(q1, λ, z) = { (qf, λ)} (C) δ(q0, λ, z) = { (q1, Sz)}; δ(q0, a, S) = { (q1, S)}, (q1, B) } δ(q0, b, λ) = { (q1, B)}, δ(q1, λ, z) = { (qf, λ)} (D) δ(q0, λ, z) = { (q1, z)}; δ(q0, a, S) = { (q1, SS)}, (q1, B) } δ(q0, b, λ) = { (q1, B)}, δ(q1, λ, z) = { (qf, λ)} a. A b. B c. C d. D

 85. Given L1 = L(a*baa*) and L2 = L(ab*) The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by a. a*b b. a*baa* c. a*ba* d. None of the above

 86. Given the production rules of a grammar G1 as S1→AB | aaB A→a | Aa B→b and the production rules of a grammar G2 as S2→aS2bS2 | bS2aS2 | λ Which of the following is correct statement? a. G1 is ambiguous and G2 is not ambiguous b. G1 is ambiguous and G2 is ambiguous c. G1 is not ambiguous and G2 is ambiguous d. G1 is not ambiguous and G2 is not ambiguous

 87. Given a grammar : S1→Sc, S→SA|A, A→aSb|ab, there is a rightmost derivation S1=>Sc =>SAC=>SaSbc. Thus, SaSbc is a right sentential form, and its handle is a. SaS b. be c. Sbe d. aSb