# UGC NET Computer Science Solved Mcqs Paper II June 2005 - Part 1

1.       Which of the following is not true?
(A) Power of deterministic automata is equivalent to power of non-deterministic automata.
(B) Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata.
(C) Power of deterministic Turing machine is equivalent to power of non-deterministic
Turing machine.
(D) All the above
2.       Identify the language which is not context - free.
(A) L = {ωωR|ωϵ{0,1}*}
(B) L = {anbn|n≥0}
(C) L = {ωω|ωϵ{0,1}*}
(D) L = {anbmcmdn | n, m≥0 }
3.       The transitive closure of a relation R on set A whose relation matrix

4.       Consider the relation on the set of non-negative integers defined by x≡y if and only if:
(A) x mod 3=3 mod y               (B) 3 mod x≡3 mod y
(C) x mod 3=y mod 3               (D) None of the above
5.       Minimum number of individual shoes to be picked up from a dark room (containing 10 pair of shoes) if we have to get atleast one proper pair:
(A) 2       (B) 20
(C) 11     (D) None of these
6.       (101011)2 = (53)b, then b is equal to:
(A) 4       (B) 8
(C) 10     (D) 16
7.       The logic expression x’yz’ + x’yz + xyz’ + xyz reduces to:
(A) x’z    (B) xyz
(C) y       (D) y z
8.       Which of the following logic has the maximum fan out?
(A) RTL              (B) ECL
(C) N MOS        (D) C MOS
9.       Which of the following binary number is the same as its 2’s complement:
(A) 1010            (B) 0101
(C) 1000            (D) 1001
10.    Identify the logic function performed by the circuit shown
(A) Exclusive-OR         (B) AND
(C) Exclusive-NOR     (D) NOR
1. 2. 