 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.

 51. Which of the following is true? a. The complement of a recursive language is recursive. b. The complement of a recursively enumerable language is recursively enumerable. c. The complement of a recursive language is either recursive or recursively enumerable. d. The complement of a context-free language is context-free.

 52. The C language is: a. A context free language b. A context sensitive language c. A regular language d. Parasble fully only by a Turing machine

 53. Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ? a. Π is NP-hard but not NP-complete b. Π is in NP, but is not NP-complete c. Π is NP-complete d. Π is neither NP-hard, nor in NP

 54. Nobody knows yet if P = NP. Consider the language L defined as follows. Which of the following statements is true ? a. L is recursive b. L is recursively enumerable but not recursive c. L is not recursively enumerable d. Whether L is recursive or not will be known after we find out if P = NP

 55. If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true ? a. L is necessarily finite b. L is regular but not necessarily finite c. L is context free but not necessarily regular d. L is recursive but not necessarily context free

 56. Consider the following deterministic finite state automaton M. Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is a. 1 b. 5 c. 7 d. 8

 57. Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S → a S b | SS | ε . Which of the following statements is true? a. G is not ambiguous b. There exist x, y, ∈ L (G) such that xy ∉ L(G) c. There is a deterministic pushdown automaton that accepts L(G) d. We can find a deterministic finite state automaton that accepts L(G)
 59. Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true ? a. L1 = {0, 1}* - L b. L1 = {0, 1}* c. L1 ⊆ L d. L1 = L
 60. The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively. a. divisible by 3 and 2 b. odd and even c. even and odd d. divisible by 2