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 cn|n>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

Go to:

2005, GATE THEORY OF COMPUTATION