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 automatonM= ({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 asS1→AB | aaBA→a | AaB→band the production rules of a grammar G2 asS2→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