2004 QUESTIONS

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


Animation Calculator Calendar Charts Clocks
Colors Conversions Counters Dates FAQs
Finance Games Health Humour Internet
LiveConnect META Navigation Netscape 4 Others
Password Random Scrolls Search Sound
Validation VRML




SOLUTIONS TO GATE PROBLEMS 
SOLUTIONS TO GATE PROBLEMS 






GATE 2004 QUESTIONS

THEORY OF COMPUTATION



Q30. The problems 3-SAT and 2-SAT are

(A) both in P

(B) both NP-complete

(C) NP-complete 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) context-free but not regular

(C) context sensitive but not context free

(D) type-0 but not context senistive

Q88. Consider the following grammar G:

S---->bS|aA|b

A---->bA|aB

B---->bB|aS|a

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) {w|Na(w)>3Nb(w)}

(B) {w|Nb(w) >3Na(w)}

(C) {w|Na(w)=3k, k in {0,1,2,---}}

(D) {w|Nb(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
Go to:
2005,
GATE THEORY OF COMPUTATION

CLICK!!! A remote control for GATE questions and answers!!