1997 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_1997

THEORY OF COMPUTATION

NOTES AND HINTS ON PROBLEMS



Q3.4 ANSWER (B)

The set of all formal languages is an uncountable set.

(A) the set of all strings is a regular set which is countably infinite. We can enumerate all strings in increasing order of length and within the same length put them in lexicograpic order. The we can number the strings we have enumerated.

(C) All regular sets are given by all regular grammars. Regular grammars are a finite description so we can enumerate them.

(D) A turing machine is a finite description over a finite alphabet. We can encode all turing machines  as strings in the alphabet {0,1} and then enumerate all strings over the alphabet and throw away all illformed strings.

Q6.4 Since epsilon does not contain 100 the answer is trivially (D).

Q6.5 ANSWER ----------- (B)

(A) Simply run the turing machine for k steps, then in a finite amount of time we know if s is accepted ornot.

(C) and (D) form the reduced grammar, if all productions do not vanish the language generated is non-empty.

(B) All nontrivial problems of turing machines are undecidable, so (B) is undecidable. The equivalence problem is decidable only for regular sets.

6.6ANSWER---------(A)

(A) is a standard DCFL. Push the elements onto the stack for w and at c change from a push to a poping state. for wR pop the strings. If the stack becomes empty at the end then accept.

(B) is a standard CFL which is not a DCFL.

(C) is a standard csl which is not a CFL, as shown by the pumping lemma for CFLs.

(D) includes palidromes of odd length so a dpda cannot guess the center of the string.

Q11(a). Note that P---------->*bi ci, i>=0

Note that Q--------------->*cj dj, j>=0

Notes that R--------------->dk ek, k>=0

From the first production we have S-------->bSe---------->bPQRe

So S-------------->b bi ci cj dj dk ek e=b^(1+1) c^(i+j) d^(j+k) e^k, i,j,k>=0

Q11(b) Consider the string bcde.

S------->bPQRe----------->b epsilon cQd    epsilon  e

-------------->* bcde

or we have the derivation

S-------------->PQR--------->bc Q   de------------->bcde

Both the above can be formualted as two distinct leftmost derivations. So bcde has two parse trees. The language always has strings with an even number of strings. We cannot have a string of lenght 2 or 0. The pairs are b,c or c,d or d,e or b,e. So bcde is the shortest string which can have two derivations. Of course be can be generated by the grammar but it has a unique derivation tree.

Q20. The minimal dfa has 6 states. A modulo 2 machine for a's and a modulo 3 machine for b's.

The state transition table of the fa is given below>

  input :  a input :  b
q00 q10 q01
q01 q11 q00
q10 q20 q11
q11 q01 q12
q12 q02 q00
q02 q12 q00

qij means i gives extra number of a's and j gives extra number of b's

Q21. Lp is nothing but init. Make all states of the fa final to accept Lp.For Ls make the final state the start state and the start state the final state and reverse the direction of the edges. Alternatives reverse the regular expression for L.

 


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