Sahrdaya College of Engineering and Technology

CS 2006

SECTION - A 1. This question consists of TWENTY-FIVE multiple questions of ONE mark each. For each question, four possible alternatives (A, B, C and D) are given, out of which ONLY ONE is correct. Indicate the correct answer in the boxes corresponding to the questions only on the FIRST sheet of the answer book. 1.1 Suppose that the expectation of a random variable X is 5. Which of the following statements is true? (a) There is a sample point at which X has the value 5. (b) There is a sample point at which X has value greater than 5. (c) There is a sample point at which X has a value greater than or equal to 5. (d) None of the above 1.2 The number of binary relations on a set with n elements is: (a) 2 n (b) 2 n (c) 2 2 n (d) None of the above 1.3 The number of binary strings of n zeroes and k ones that no two ones are adjacent is (a) n 1Ck − (b) nCk (c) 1 nCk + (d) None of the above 1.4 Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite automation that recognizes the language represented by this regular expression contains (a) n states (b) n + 1 states (c) n + 2 states (d) None of the above 1.5 Context-free languages are closed under: (a) Union, intersection (b) Union, Kleene closure (c) Intersection, complement (d) Complement, Kleene closure 1.6 Let LD be the set of all languages accepted by a PDA by final state and L E the set of all languages accepted by empty stack. Which of the following is true? (a) L D = LE (b) L D ⊃LE (c) L E = LD (d) None of the above 1.7 Which of the following expressions is not equivalent to x ? (a) x NAND X (b) x NOR x (c) x NAND 1 (d) x NOR 1