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


GATE_1990
THEORY OF COMPUTATION
NOTES AND HINTS TO SOLUTIONS
Q3(IV) ANSWER(A) AND (D)
The recursive languages are a superset of the cfls. Only we are ignoring epsilon which cannot be in any csl or recursive set.
pda can accept only the cfls, {an bn cnn>1} is a csl and not a cfl and no pda can accept it. The r.e languages are the Type 0 languages which are a superset of the recursive sets.
Turing machines accept all the recursive set and more(i.e. the r.e. sets also).
Q3(vii) ANSWER(B) AND (D)
No nontrivial problem is decidable for an arbitary turing machine. Given an arbitrary turing machine we cannot decide if it prints a specific letter(the Printing problem) or computes the product of two numbers.
We can decide if it halts after 10 *phi steps provided phi is a constant, not otherwise.
Turing machines have the capability of multiplication, but whether a given turing machine will compute the product of two numbers is not decidable as we cannot decide anything for an arbitrary turing machine.
So (D) depends on how the problem is posed.
Q15(a) The given grammar is a right linear grammar so it generates a regular set.
Construct a state diagram from the grammar, it is easily seen to yield a(bx)*bc as the set accepted by the finite automata.
Q15(b) A proper printed version of the question is not available.
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 