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


GATE_1999
THEORY OF COMPUTATION
HINTS AND SOLUTIONS TO PROBLEMS
Q1.6 The sets accepted by pda by final state or empty stack are alternative definitions for the sets accepted and in both cases it is the cfls that are accepted
.
CS6(a) ANSWERNO
If we choose A to be (0+1)* the B can be any formal language.
QCS6(b) We must check for strings in L1'intersection L2 and L2'intersection L1.
If L1 is contained in L2 then L1 is not contained in the complement of L2. If L1 is contained in L2 then its complement must have string in L2.
CS7. The language is not a cfl. Intersect the language with0*1*c0*1*, the resulting language can be shown not to be a cfl by an application of the pumping lemma.
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 