CLICK ON A PICTURE BELOW FOR PREVIOUS GATE QUESTIONS 1987 ONWARDS IN THE THEORY OF COMPUTATION


GATE 2003 QUESTIONS
THEORY OF COMPUTATION
Q12. Ram and Shyam have been asked to show that a certain problem II is NPcomplete. Ram shows a polynomial time reduction frin tge 3SAT problem to II, and Shyam shows a polynomial time reduction fro II to 3SAT. Which of the following can be inferred from these reductions?
(a) II is NPhard but not NPcomplete
(b) II is is NP, but is not NPcomplete
(c) II is NPcomplete
(d) II is neither NPhard. nor in NP
Q13. Nobody knows yet if P=NP. Consider the language L defined as follows:
L=(0+1)* if P=NP
L=null set otherwise
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
Q14. The regular expression 0*(10*)* denotes the same set as
(a) (1*0)*1* (b) 0 + (0 +10)*
(c) (0+1)*10(0+1)* (d) none of the above
Q15. 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.
Q50. 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
Q51. Let G =({S},{a,b},R,S) be a context free grammar where the rule set R is
S>aSbSSe
Which of the following statements is true?
(a) G is not ambiguous.
(b) There exist x, y in L(G) such that xy is not in 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)
Q52. Consider two languages L1 and L2 each on the alphabet X. Let f:X>X be a polynomial time computable bijection such that [for all x, x in L1 iff f(x) is in L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
(a) L1 is in P and L2 is finite.
(b) L1 is in NP and L2 is in P.
(c) L1 is undecidable and L2 is decidable.
(d) L1 is recursively enumerable and L2 is recursive.
Q53. A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0,1,B} and its input alphabet is {0,1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table
0  1  B  
q0  q1, 1, R  q1, 1, R  Halt 
q1  q1, 1, R  q0, 1, L  q0, B, L 
The table is interpreted as illustrated below:
The entry (q1,1,R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes a 1 on the same tape square, moves its tape head one position to the right and transitions to state q1.
(a) M does not halt on any string in (0+1)+
(b) M does not halt on any string in(00+1)*
(c) M halts on all strings ending in a 0
(d) M halts on all strings ending in a 1
Q54. Define languages L0 andL1 as follows:
L0={<M,w,0> M halts on w}
L1={<M,w,1> M does not halt 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 U 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
Note:L' is the complement of L
Q55. 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 is a subset of L (d) L1 = l
ANS  
1987  1988  1989 
1990  1991  1992 
1993  1994  1995 
1997  1998  1999 
2000  2001  2002 
2003  2004  1987 
QUES  
1987  1988  1989 
1990  1991  1992 
1993  1994  1995 
1997  1998  1999 
2000  2001  2002 
2003  2004  1987 