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


GATE_1988
THEORY OF COMPUTATION
HINTS AND SOLUTIONS
Q2(viii) State the halting problem of turing machines.
It is not decidable(i.e. no algorithm exists) which can decide if an arbitary turing machine on a given input will ever halt. No halting turing machine(i.e.algorithm) exists to solve this problem.
Q2(ix) The language L={an bn 0<n<327th prime number} is a finite set and hence regular.
Q15.M2 has three copies of M.
Case(i): F2=A. In this case the first copy behaves as the same as M and the other two are don't care conditions. So the language accepted is L.
Case(ii): F2=B. In this case the second copy starts from any state and proceed to the output. So if the head of a string reaches a final state then we accept i.e. we accept any string of L that makes an excursion to the final state..
Case (iii) In this case we accept Init(L).
Case (iv) r is not specified in the final states of M2 so we accept the empty set.
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 