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


GATE_1996
THEORY OF COMPUTATION
HINTS AND SOLUTIONS TO PROBLEMS
Q1.8 ANSWER (C)
(i) This says even number of 0s plus odd no of 0s i.e. 0*
(ii) This says evenumbr of 0s
(iii) This says all 0s
(iv) This says only odd no of 0s
Q1.9 ANSWER(d)
The hating problem is undecidable for turing machines, the equivalence of cfs and ambiguity of a cfg are standard undecidable problems.
The equivalence of fa is decidable. Convert each to the minimal dfa and see if the graphs are isomorphic.
Q1.10ANSWER(D)
The first three are three standard cfls which are not regular, by the pumping lemma for regular sets.
(D) represents a*b* which is regular.
Q2.9ANSWER(B)
(A) is excluded as init contains 0011
(C) is excluded as init contains 00000
(D) is allowed as init contains any sequence of 0s and 1s in any order.
Q11. Eliminating A>e we get the rules
S>ABCBACBC
A>a
By eliminating B>e we get the rules
S>ACAACC
B>b
After eliminating the e rules we get
S>ABACABCBACBCACAACC
A>aAA
B>bBB
C>D
After the elimination of the unit production we get
S>ABACABCBACBCACAACd
A>aAA
B>bBB
C>D
Q12. The terminolgy of & transitions is not clear in the printed version of the paper available to me. For e moves simply put e transitions from state A to state C. A should be final as M2 accepts epsilon.
Q13. The only rules to be added are those which guess the center of the string
for (3) add{(q1,aa),(q2,e)}
for (4) add {(q1,bb),(q2,e))
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 