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)
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).{a} U L(abb*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
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).Context free but not 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
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Both S1 and S2 are correct

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).B

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).a*ba*

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).G1 is ambiguous and G2 is 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
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).aSb

88. The equivalent production rules corresponding to the production rules

S→Sα1|Sα2|β1|β2 is
a. S→β1 | β2, A→α1A | α2A | λ
b. S→β1 | β2 | β1A | β2A,       A→α1A | α2A
c. S→β1 | β2, A→α1A | α2A
d. S→β1 | β2 | β1A | β2A,       A→α1A | α2A | λ
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).S→β1 | β2 | β1A | β2A,       A→α1A | α2A | λ

89. Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively transition table as given below

The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
a. 5
b. 4
c. 3
d. 2
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).3

90. The grammar with production rules S → aSb |SS|λ generates language L given by:
a. L = {w∈{a, b}* | na(w) = nb(w) and na(v) ≥ nb(v) where v is any prefix of w}
b. L = {w∈{a, b}* | na(w) = nb(w) and na(v) ≤ nb(v) where v is any prefix of w}
c. L = {w∈{a, b}* | na(w) ≠ nb(w) and na(v) ≥ nb(v) where v is any prefix of w}
d. L = {w∈{a, b}* | na(w) ≠ nb(w) and na(v) ≤ nb(v) where v is any prefix of w}
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).L = {w∈{a, b}* | na(w) = nb(w) and na(v) ≥ nb(v) where v is any prefix of w}

Page 9 of 13