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

Go to:

2005, GATE THEORY OF COMPUTATION