121.  Which of the following is not true? 
a.  Power of deterministic automata is equivalent to power of nondeterministic automata. 
b.  Power of deterministic pushdown automata is equivalent to power of nondeterministic pushdown automata. 
c.  Power of deterministic Turing machine is equivalent to power of nondeterministic Turing machine. 
d.  All the above 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Power of deterministic pushdown automata is equivalent to power of nondeterministic pushdown automata.

122.  Identify the language which is not context  free. 
a.  L = {ωωRωϵ{0,1}*} 
b.  L = {a^nb^nn≥0} 
c.  L = {ωωωϵ{0,1}*} 
d.  L = {a^nb^mc^md^n  n, m≥0 } 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).L = {a^nb^nn≥0}

123.  The contextfree languages are closed for: (i) Intersection (ii) Union (iii) Complementation (iv) Kleene Star 
a.  (i) and (iv) 
b.  (i) and (iii) 
c.  (ii) and (iv) 
d.  (ii) and (iii) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).(ii) and (iv)

124.  Grammars that can be translated to DFAs: 
a.  Left linear grammar 
b.  Right linear grammar 
c.  Generic grammar 
d.  All of these 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Right linear grammar

125.  The language accepted by a Push down Automata: 
a.  Type0 
b.  Type1 
c.  Type2 
d.  Type3 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Type2

126.  In parallel algorithm design, the process of grouping tasks into larger tasks in order to improve performance: 
a.  Agglomeration 
b.  Domain Decomposition 
c.  Mapping 
d.  None of these 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).Agglomeration

127.  Recursive Descent Parsers are a type of: 
a.  LL parsers 
b.  LR parsers 
c.  LALR parsers 
d.  SLR parsers 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).LL parsers

128.  If language L={0,1}*, then the reversed language L^R = 
a.  {0,1}* 
b.  {} 
c.  {0}* 
d.  {1}* 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).{0,1}*

129.  Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions. Consider the following: (i) L(s) ⊆ L(r) and L(s) ⊆ L(t) (ii) L(r) ⊆ L(s) and L(s) ⊆ L(t) Choose the correct answer from given below: 
a.  Only (i) is correct 
b.  Only (ii) is correct 
c.  Both (i) and (ii) are correct 
d.  Neither (i) nor (ii) is correct 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).Only (i) is correct

130.  Consider the language L given by L = {2^(nk) ∣ k>0, and n is nonnegative integer number} The minimum number of states of finite automaton which accepts the language L is 
a.  n 
b.  n+1 
c.  n(n+1)/2 
d.  2^n 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).n+1
