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.

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 context-free 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
derivation tree
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^n|n≥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 = {w|na(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. Single-tape-turing machine and multi-dimensional turing machine
b. Multi-tape turing machine and multi-dimensional turing machine
c. Deterministic push down automata and non-deterministic pushdown automata
d. Deterministic finite automata and Non-deterministic finite automata
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Deterministic push down automata and non-deterministic pushdown automata

46. Which of the following statements is false?
a. Every context-sensitive 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!
Answer: (b).t

48. A t-error correcting q-nary linear code must satisfy the following, Where M is the number of code words and X is
error correcting q-nary linear code
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 LZ-coding (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

Page 5 of 13