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