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 : L2L1 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.  Nondeterministic 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→SAA, A→aSbab, 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α1Sα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 Nondeterministic 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}
