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