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


GATE 2004 QUESTIONS
THEORY OF COMPUTATION
Q30. The problems 3SAT and 2SAT are
(A) both in P
(B) both NPcomplete
(C) NPcomplete and in P respectively
Q86. The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively
(A) divisible by 3 and 2
(B) odd and even
(C) even and odd
(D) divisible by 2 and 3
Q87. The language {a^m b^n c^(m+n)m,n>=1} is
(A) regular
(B) contextfree but not regular
(C) context sensitive but not context free
(D) type0 but not context senistive
Q88. Consider the following grammar G:
S>bSaAb
A>bAaB
B>bBaSa
Let Na(w) and Nb(w) denote the number of a's and b's in a string w respectively. The language L(G) a subset of {a,b}+ generated by G is
(A) {wNa(w)>3Nb(w)}
(B) {wNb(w) >3Na(w)}
(C) {wNa(w)=3k, k in {0,1,2,}}
(D) {wNb(w) =3k, k in {0,1,2,}}
Q89. L1 is a recursively enumerable language over X. An algorithm A effectively enumerates its words w1,w2,w3,. Define another language L2 over XU{#} as {wi#wj:wi, wj in L1, i<j}. Here # is a new symbol. Consider the following assertions:
S1: L1 is recursive implies L2 is recursive
S2:L2 is recursive implies L1 is recursive
Which of the following statements is true?
(A) Both S1 and S2 are true
(B) S1 is true but S2 is not necessarily true
(C) S2 is true but S1 is not necessarily true
(D) Neither is necessarily true
Q7(IT) Which one of the following regular expressions is NOT equivalent to the regular expression (a+b+c)*?
(A) (a*+b*+c*)*
(B)(a*b*c*)*
(C)((ab)* +c*)*
(D)(a*b* +c*)*
Q40(IT). Let M=(K,X,G,D,s,F) be a pushdown automaton, where
K={s,f}, F={f}, X={a,b} and G={a} and
D={((s,a,e),(s,a)),((s,b,e),(s,a)),((s,a,e),{f,e)),((f,a,a),(f,e)),((f,b,a).(f,e))}
Which one of the following strings is not a member of L(M)?
(A) aaa
(B) aabab
(C) baaba
(D) bab
Q41(IT). Let M=(K,X,ð,s,F) be a finite state automaton, where
K=(A,B}, X={a,b}, s=A, F={B},
ð(A,a)=A, ð(A,b)=B, ð(B,a)=B, and ð(B,b)=A
A gramar to generate the language accepted by M can be specified as G=(V,X,R,S), where V=K U X, and S=A.
Which one of hte followingst of rules will make L(G)=L(M)?
(A) {A>aB,A>bA, B>bA, B>aA, B>e}
(B) {A>aA,A>bB, B>aB, B>bA, B>e}
(C) {A>bB,A>aB, B>aA,B>bA,A>e}
(D) {A>aA, A>bA, B>aB, B>A, A>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 