 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.

 61. Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has ................ equivalence classes. a. 2 b. 4 c. 5 d. 6

 62. Let L = {0^n1^n | n≥0} be a context free language. Which of the following is correct? a. L’ is context free and L^k is not context free for any k≥1 b. L’ is not context free and L^k is context free for any k≥1 c. Both L’ and L^k is for any k≥1 are context free d. Both L’ and L^k is for any k≥1 are not context free

 63. Given a Turing Machine M = ({q0,q1,q2,q3}, {a,b}, {a,b,B}, δ, B, {q3}) Where δ is a transition function defined as δ(q0,a) = (q1,a,R) δ(q1,b) = (q2,b,R) δ(q2,a) = (q2,a,R) δ(q2,b) = (q3,b,R) The language L(M) accepted by the Turing Machine is given as: a. aa*b b. abab c. aba*b d. aba*

 64. Match the following : List - I                                                             List - II (a) {a^n b^n|n > 0} is a deterministic                  (i) but not recursive language context free language         (b) The complement of {a^n b^n a^n|n > 0}         (ii) but not context free language is a context free language (c) {a^n b^n a^n} is context sensitive language (iii) but can not be accepted by a deterministic pushdown automation (d) L is a recursive language                         (iv) but not regular Codes :      (a)   (b)   (c)   (d) a. (i)   (ii)   (iii)   (iv) b. (i)   (ii)   (iv)   (iii) c. (iv) (iii)  (ii)    (i) d. None of the above is correct match

 65. The language of all non-null strings of a’s can be defined by a context free grammar as follow : S→a S|S a| a The word a^3 can be generated by ................ different trees. a. Two b. Three c. Four d. Five

 66. The context free grammar given by S→XYX X→aX|bX|λ Y→bbb generates the language which is defined by regular expression: a. (a+b)*bbb b. abbb(a+b)* c. (a+b)*(bbb)(a+b)* d. (a+b)(bbb)(a+b)*

 67. There are exactly ................ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state. a. 64 b. 256 c. 1024 d. 5832