1996 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_1996

THEORY OF COMPUTATION

HINTS AND SOLUTIONS TO PROBLEMS



Q1.8 ANSWER (C)

(i) This says even number of 0s plus odd no of 0s i.e. 0*

(ii) This says evenumbr of 0s

(iii) This says all 0s

(iv) This says only odd no of 0s

Q1.9 ANSWER----------(d)

The hating problem is undecidable for turing machines, the equivalence of cfs and ambiguity of a cfg are standard undecidable problems.

The equivalence of fa is decidable. Convert each to the minimal dfa and see if the graphs are isomorphic.

Q1.10ANSWER--------------(D)

The first three are three standard cfls which are not regular, by the pumping lemma for regular sets.

(D) represents a*b* which is regular.

Q2.9ANSWER--------------(B)

(A) is excluded as init contains 0011

(C) is excluded  as init contains 00000

(D) is allowed as init contains any sequence of 0s and 1s in any order.

Q11. Eliminating A------------>e we get the rules

S--------->ABC|BAC|BC

A--------->a

By eliminating B----------->e we get the rules

S----------->AC|AAC|C

B---------->b

After eliminating the e rules we get

S--------->ABAC|ABC|BAC|BC|AC|AAC|C

A--------->aA|A

B--------->bB|B

C-------->D

After the elimination of the unit production we get

S---------->ABAC|ABC|BAC|BC|AC|AAC|d

A----->aA|A

B--------->bB|B

C---------->D

Q12. The terminolgy of & transitions is not clear in the printed version of the paper available to me. For e moves simply put e transitions from state A to state C. A should be final as M2 accepts epsilon.

Q13. The only rules to be added are those which guess the center of the string

for (3) add{(q1,aa),(q2,e)}

for (4) add {(q1,bb),(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
Go to:
2005,
GATE THEORY OF COMPUTATION

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