1990 ANSWERS

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_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

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