2004 ANSWERS

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

THEORY OF COMPUTATION

HINTS AND SOLUTIONS TO PROBLEMS



THE GOEDEL TURING SOCIETY


v

Q30. ANSWER----------(C)

The problem 3-SAT is NP-complete wheras the problem 2_SAT has a polynomial time algorithm.

Q86. ANSWER----(A)

The machine accepts set of all strings where the 1's are divisible by three and the 0's divisible by 2.

Try 111 it is accepted, this throws out choices (B),(C) and (D)

Q87. ANSWER---------(B)

One can easily design a dpda which pushes a's and b's onto the stack and for every c in the input it pops and a or a b.

Q88. ANSWER------(C)

S----->b+ by the first set of rules S--->bS|S, this eliminates choices (A) and (D)

S-------->aaa by S--->*aA---->*aaB--------->aaa and this eliminates (B)

Q89. ANSWER----------(A)

If L1 is recursive then we enumerate L2 and find out wj in a finite amount of time, and then enumerate strings <wj in lexicographic order in a finite amount of time.

If L2 is recursive enumerate it in lexicographic order of wj etc.

Q7(IT) ANSWER---------(c)

(a* +b* +c*)=(a+b+c+other strings)*=(a+b+c)*

for (B) we have the standard identity (r*s*)*=(r+s)*

for (D) we have (a*b*+c*)=(a+b+c+other strings)*=(a+b+c)*

for C we have a is not a substring

Q9(IT) ANSWER----(C)

Nondeterminism makes a difference to the pda. The language {wwR} is accepted by a nondeterministic pda but not by a deterministic pda.

(A) is the standard theorem: there exist inherently ambiguous languages

(B) is the definition of ambiguity

(D) all finite sets are regular sets

Q40(IT) ANSWER------(B)

The fastest way is to trace out all the strings.

Q41(IT) ANSWER-----(B)

The move

(A,a)=A demands the rule A---->aA and this excludes (A) and (C)
The move

(A,b)=B demands the rule A--->bB and this excludes (D)


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!!