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


GATE_1991
THEORY OF COMPUTATION
HINTS AND NOTES ON SOLUTIONS
Q3(xiii)ANSWER(A) and (C)
From an examination of the three regular expressions t contains a 0 wheras the other two do not. So L(t) cannot be a subset of the other two sets. This excludes (D).
L(r) contains 100 wheras the other two do not. So L(r) cannot be a subset of the other two. This excludes (B).
Note that (A) and (C) are the same.
Q3(xiv) ANSWER(D)
The regular sets are the smallest class that contain all the finite sets.
Q17(a) If we take a turing machine and take away its ink it becomes a 2DFA or 2NFA. We have the standard theorem that these accept only the regular sets.
Q17(b) The nfa for the machine over {0,1} is given below:
input 0  input 1  
(start state) H  H  H,P 
P  M  M 
M  *C  *C 
*C     
The equivalent minimal dfa has 8 states as can be shown by constructing the dfa and minimising it. This is the example of a nfa to dfa conversion which requires an exponential number of states.
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 