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


GATE_2000
THEORY OF COMPUTATION
HINTS AND SOLUTIONS TO PROBLEMS
Q1.4 ANSWER(C)
(a+b*) is the same as (a+b+b*)=(a+b)*
Q1.5 ANSWER(B)
L is (00)+ as the 0's always occur in pairs.
(D) is not correct as the grammar is a cfg.
(A) is excluded as 00 is in the language generated.
Q2.9 ANSWER(A)
For P1 simply trace the path through the state diagram of the finite automata.
For P2 take the reduced grammar in the CNF and draw the graph of the grammar. If cycles exist the cfl is infinite else it is finite.
Q.CS7(a). The finite automat state transition diagram is given below.
input: 0  input:1  
*q0  Reject  q1 
*q1  q0  Reject 
Reject  Recject  Reject 
By examination we find all the states can be distinguished on some input string. So the minimal automata is the same as that given above.
Q3.7(b)By examination it seen that the first production will demand the same number of b's as a's.A can optionally yield extra b's. So we have j>i as the required condition.
Q.CS8.(a) q0 is a push state which pushes 0's and 1's onto the stack. So we have
del(q0,2,s)=(q0,2.s)
q1 is a pop state so we have
del(q1,2,2.s)=(q1,s)
QCS8(b) q0 and q1 will be push states where for every 0 in the input we nondeterministially push one or two 0's onto the stack.
del(q0,0,s)={(q0,0.s),(q2,0.s)}
del(q2,e,s)={(q0,0.s)}
When a 1 occurs we nondeterministically unstack one or two 0's from the stack.
del(q0,1,0.s)={(q1,s)}
del(q0,e,s)={(q1,s)}
In q1 the pop state we unstack one or two 0's for a 1 in the input.
del(q1,1,0.s)={(q1,s),(q2,s)}
del(q2,1,0.s)={(q1,s)}
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 