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.
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).The complement of a recursive language is recursive.

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).A context free language

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Π is NP-complete

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).L is recursive

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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
deterministic finite state automaton
a. 1
b. 5
c. 7
d. 8
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).7

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)
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).There is a deterministic pushdown automaton that accepts L(G)

58. Define languages L0 and L1 as follows :

L0 = {< M, w, 0 > | M halts on w}
L1 = {< M, w, 1 > | M does not halts on w}

Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L = L0 ∪ L1. Which of the following is true ?
a. L is recursively enumerable, but L' is not
b. L' is recursively enumerable, but L is not
c. Both L and L' are recursive
d. Neither L nor L' is recursively enumerable
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).L is recursively enumerable, but L' is not

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 ?
NFA
a. L1 = {0, 1}* - L
b. L1 = {0, 1}*
c. L1 ⊆ L
d. L1 = L
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).L1 = {0, 1}*

60. The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively.
finite state machine
a. divisible by 3 and 2
b. odd and even
c. even and odd
d. divisible by 2
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).divisible by 3 and 2

Page 6 of 14