2001 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_2001

THEORY OF COMPUTATION

HINTS AND SOLUTIONS TO PROBLEMS



 

Q1.4 ANSWER----------(A)

S1 is nothing but (00)+, a regular expression and hence denotes a regular set.

S2 is not a regular set as seen from the pumping lemma for regular sets.

Q1.5 ANSWER-------(B)

The union of two cfls is a cfl.

The deterministic and nondeterministic models of the pda are not the same.

The cfls are not closed under intersection or complement.

Q1.6 ANSWER-----(B)

In the worst case we require the entire subset machine in converting a nfa to a dfa.

Q2.5 ANSWER--------------(D)

We have to take the product of a modulo 6 machine and a modulo 8 machine.

Q2.6 ANSWER-------------(D)

L1,L2 and L4 are standard non-regular sets.

L3 is the set (00)*

Q2.7 ANSWER-----------(B)

Just start the turing machine and sit in front of it. If it visits the state q we will know in a finite amount of time else we may never know.


 

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