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


GATE 1999 PROBLEMS
THEORY OF COMPUTATION
SECTION A
Q1.4 Consider the regular expression (0+1)(0+1).....n times. The minimum state finite automaton that recognizes the language represented by this regular expression contains
(A) n states (B) n+1 states
(C) n+2 states (D) None of the above
Q1.5 Contextfree languages are closed under:
(A) Union, intersection
(B) Union, Kleene closure
(C) Intersection, complement
(D) Complement, Kleene closure
Q1.6 Let Ld be the set of all languages accepted by a PDA by final state and Le be the set of all languages accepted by empty stack. Which of the following is true?
(A) Ld = Le
(B) Ld is a superset of Le
(C) Ld is a subset of Le
(D) None of the abovE
SECTION B
CS6 (a) Given that A is regular and (AUB) is regular, does it follow that B is necessarily regular? Justify your answer.
(b) Given two finite automata M1, M2 outline an algorithm to decide if L(M1) is a strict subset of L(M2).
CS7. Show that the language L = {xcxx in {0,1}* and c is a terminal symbol} is not context free, with c not the same as o or 1.
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 