CLICK ON A PICTURE BELOW FOR PREVIOUS GATE QUESTIONS 1987 ONWARDS IN THE THEORY OF COMPUTATION


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