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


GATE 1992 PROBLEMS
THEORY OF COMPUTATION
PART A
Q2(xii) Which of the following regular expression identities are true?
(A) r(*) = r*
(B) (r*S*)* = (r + s)*
(C) (r + s)* = r* + s*
(D) r*s* = r* + s*
Q2(xviii) If G is a contextfree grammar and w is a string of length l in L(G), how long is a derivation of w in G, if G is in the Chomky normal form?
(A) 2l (B) 2l + 1 (C) 2l  1 (D) l
Q2(xix) Contextfree languages are
(A) closed under union (B) closed under complementation
(C) closed under intersection (D) closed under Kleene closure
Q2(xx) In which of the cases stated below is the following statement true?
"For every nondeterministic machine M1 there exists an equivalent deterministic machine M2 recognizing the same language".
(A) M1 in a nondeterministic finite automaton.
(B) M1 is a nondeterministic PDA
(C) M1 is a nondeterministic Turing machine
(D) For no machine M1 is the above statement True
PART B
Q16 Which of the following three statements are true? Prove your answer.
(i) The union of two recursive languages is recursive.
(ii) The language {0^n  n is a prime } is not regular.
(iii) Regular languages are closed under infinite union.
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 