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


GATE 1996 PROBLEMS
THEORY OF COMPUTATION
SECTION A
Q1.8 Two of the following four regular expressions are equivalent which two? (e is the empty string).
(i) (00)*(e+0) (ii) (00)* (iii) 0* (iv) 0(00)*
(A) (i) and (ii) (B) (ii) and (iii) (C) (i) and (iii) (D) (iii) and (iv)
Q1.9 Which of the following statements is false?
(A) The Halting problem of Turing machines is undecidable.
(B) Determining whether a context free grammar is ambiguous is undecidable.
(C) Given two arbitrary context free grammars G1 and G2 it is undecidable whether L(G1)=L(G2).
(D) Given two regular grammars G1 and G2 it is undecidable whether L(G1)=L(G2).
Q1.10 Let L be a subset of X* where X={a,b}. Which of the following is true?
(A) L = {x x has an equal number of a's and b's} is regular.
(B) L = {a^n b^n n>=1} is regular.
(C) L = {x  x has mores a's than b's} is regular.
(D) L = {a^m b^n  m>=1, n>=1} is regular
Q2.8 If L1 and L2 are context free languages and R a regular set, one of the languages below is not necessarily a contextfree language. Which one?
(A) L1L2 (B) L1 intersection L2 (C) L1 intersection R (D) L1 U L2
Q2.9 Define for a contextfree language L over {0,1}, init(L)={uuv in L for some v in {0,1}*}, in other words init(L) is the set of prefixes of L.
Let L= {ww is nonempty and has an equal number of 0.s and 1's}
Then init(L) is
(A) the set of all binary strings with an unequal number of 0's and 1's
(B) the set of all binary strings including the null string
(C) the set of all binary strings with exactly one more 0's than the number of 1's or one more 1 then the number of 0's.
(D) None of the above
SECTION B
Q11. Let G be a contextfree grammar where G= ({S,AB,C},{a,b,d},P,S} with the productions in P given below.
S>ABAC
S>aAe
S>bBe
C>d
(e denotes the null string).
Transform the grammar G to an equivalent contextfree grammar that has no eproductions and no unit productions. ( A unit production is of the form x>y, where x and y are nonterminals).
Q12. Given below are the transiton diagrams for two finite state machines M1 andM2 recognising languages L1 and L2 respectively.
(a) Display the transition diagram for a machine that recognizes L1L2 obtained from transition diagrams for M1 and M2 by adding only & transitions and no new states.
(b) Modify the transition diagram obtained in part (a) to obtain a transition diagram for a maachie that recognizes (L1L2) by adding only e transitions and no new states.
(Final states are enclosed in double circles).
Q13. Let Q = ({q1,q2},{a,b},{a,b,Z},f,{q1,q2},Z,0) be a push down automaton accepting by empty stack the language which is the set of all nonempty even palidromes over the set {a,b}. Below is an incomplete specification of the transitions for Q. Complete the specification. The top of the stack is assumed to be at the right end of the string representing the stack contents.
(1) f(q1,a,Z) = {(q1,Za)}
(2) f(q1,b,Z) = {(q1,Z)}
(3) f(q1,a,a)= {,}
(4) f(q1,b,b)={,}
(5) f(q2,a,a)={(q2,e)}
(6) f(q2,b,b)={(q2,e)}
(7) f(q2,e,Z)={(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 