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