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


GATE_2002
THEORY OF COMPUTATION
HINTS AND SOLUTIONS TO PROBLEMS
Q1.7 ANSWER(B)
If the stack is limited to 10 items then the pda can remember the contents of the stack in its finite control. Thus the pda becomes a finite automata. Hence the language accepted is regular.
Q2.14 ANSWER (A)
The recursive sets are closed under complement, wheras the r.e sets are not. The cfls are not closed under complement.
CS14. (a) M operates with input w
(b) When M halts it starts M'
(c) Rice's theorem, the moidfied version of M' accepts the set of entire strings over the terminal vocabulary or the empty set depending on whether the universal lanugae accepted by M is decidable or not.
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 