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


GATE 2002 PROBLEMS
THEORY OF COMPUTATION
Q1.7 The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as
A. Context Free
B. Regular
C. Deterministic Context Free
D. Recursive
Q2.14 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.
CS14. The aim of the following question is to prove that the language {M M is the code of a Turing Machine which, irrespective of the input, halts and outputs a 1} is undecidable. This is to be done by reducing from the language {M',xM' halts on x}, which is known to be undecidable. In parts (a) and (b) describe the tow main steps in the construction of M. In part(c) describe the key property which relates the behaviour of M on its input w to the behaviour of M' on x.
(a) On input w, what is the first step that M must make?
(b) On input w, based on the outcome of the first step, what is the second step that M must make?
(c) What key property relates the behaviour of M on w to the behaviour of M' on x?
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 