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 contextfree language is contextfree. 
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 NPcomplete. Ram shows a polynomial time reduction from the 3SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3SAT. Which of the following can be inferred from these reductions ? 
a.  Π is NPhard but not NPcomplete 
b.  Π is in NP, but is not NPcomplete 
c.  Π is NPcomplete 
d.  Π is neither NPhard, nor in NP 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Π is NPcomplete

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 
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 nonaccepting state and by changing the nonaccepting 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 
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. 
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
