1988 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_1988

THEORY OF COMPUTATION

HINTS AND SOLUTIONS



 

Q2(viii) State the halting problem of turing machines.

It is not decidable(i.e. no algorithm exists) which can decide if an arbitary turing machine on a given input will ever halt. No halting turing machine(i.e.algorithm) exists to solve this problem.

Q2(ix) The language L={an bn |0<n<327th prime number} is a finite set and hence regular.

Q15.M2 has three copies of M.

Case(i): F2=A. In this case the first copy behaves as the same as M and the other two are don't care conditions. So the language accepted is L.

Case(ii): F2=B. In this case the second copy starts from any state and proceed to the output. So if the head of a string  reaches a final state then we accept i.e. we accept any string of L that makes an excursion to the final state..

Case (iii) In this case we accept Init(L).

Case (iv) r is not specified in the final states of M2 so we accept the empty set.



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