1995 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_1995

THEORY OF COMPUTATION

HINTS AND SOLUTIONS TO PROBLEMS



 

Q1.10 ANSWER-------(C)

The last rule has two symbols on the left hand side and the right hand sides of all the rules is as lone as or longer than the left hand side.

Q2.20 ANSWER-------------(A)

The language is a standard cfl which is generated by the productions in I. II gives a regular set and the given language is not regular.

Q2.24ANSWER---------------(C)

L U R is the same as the set of all strings over {0,1} and hence is regular. R is a standard cfl that is not regular.

Q11. For every n there is exactly one string in L. There are only a finite number of strings of length n. Create so many copies of the turing machine and run them one for each string of length n. One of the copies will terminate in polynomial time then terminate the others which accept strings in the complement of L. So we can decide if a string is in L or not in a polynomial amount of time so the complement of L is also in NP.


 

 

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