2002 QUESTIONS

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


Animation Calculator Calendar Charts Clocks
Colors Conversions Counters Dates FAQs
Finance Games Health Humour Internet
LiveConnect META Navigation Netscape 4 Others
Password Random Scrolls Search Sound
Validation VRML




SOLUTIONS TO GATE PROBLEMS 
SOLUTIONS TO GATE PROBLEMS 






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 context-free language is context-free.

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',x|M' 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
Go to:
2005,
GATE THEORY OF COMPUTATION

CLICK!!! A remote control for GATE questions and answers!!