41.  Given the following statements : (A) A class of languages that is closed under union and complementation has to be closed under intersection. (B) A class of languages that is closed under union and intersection has to be closed under complementation. Which of the following options is correct? 
a.  Both (A) and (B) are false 
b.  Both (A) and (B) are true 
c.  (A) is true, (B) is false 
d.  (A) is false, (B) is true 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).(A) is true, (B) is false

42.  Let G = (V,T,S,P) be a contextfree grammar such that every one of its productions is of the form A→v, with v = K>1. The derivation tree for any W ϵ L(G) has a height h such that 
a.  1 
b.  2 
c.  3 
d.  4 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).4

43.  Given the following two languages: L1 = {a^nb^nn≥0, n≠100} L2 = {w ϵ {a,b,c}* na(w) = nb(w) = nc(w)} Which of the following options is correct? 
a.  Both L1 and L2 are not context free language 
b.  Both L1 and L2 are context free language 
c.  L1 is context free language, L2 is not context free language 
d.  L1 is not context free language, L2 is context free language 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).L1 is context free language, L2 is not context free language

44.  Given the following two statements: A. L = {wna(w) = nb(w)} is deterministic context free language, but not linear. B. L = {an bn} U {an b2n} is linear, but not deterministic context free language. Which of the following options is correct? 
a.  Both (A) and (B) are false 
b.  Both (A) and (B) are true 
c.  (A) is true, (B) is false 
d.  (A) is false, (B) is true 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Both (A) and (B) are true

45.  Which of the following pairs have different expressive power? 
a.  Singletapeturing machine and multidimensional turing machine 
b.  Multitape turing machine and multidimensional turing machine 
c.  Deterministic push down automata and nondeterministic pushdown automata 
d.  Deterministic finite automata and Nondeterministic finite automata 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Deterministic push down automata and nondeterministic pushdown automata

46.  Which of the following statements is false? 
a.  Every contextsensitive language is recursive 
b.  The set of all languages that are not recursively enumerable is countable 
c.  The family of recursively enumerable languages is closed under union 
d.  The families of recursively enumerable and recursive languages are closed under reversal 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).The set of all languages that are not recursively enumerable is countable

47.  Let C be a binary linear code with minimum distance 2t + 1 then it can correct upto ............bits of error. 
a.  t + 1 
b.  t 
c.  t  2 
d.  t/2 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).t

48.  A terror correcting qnary linear code must satisfy the following, Where M is the number of code words and X is 
a.  q^n 
b.  q^t 
c.  q^n 
d.  q^t 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).q^n

49.  From the given data below: a b b a a b b a a b which one of the following is not a word in the dictionary created by LZcoding (the initial words are a, b)? 
a.  a b 
b.  b b 
c.  b a 
d.  b a a b 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).b a a b

50.  The number of strings of length 4 that are generated by the regular expression (0+1+2+3+)*, where  is an alternation character and {+, *} are quantification characters, is: 
a.  08 
b.  09 
c.  10 
d.  12 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).10
