CLICK ON A PICTURE BELOW FOR PREVIOUS GATE QUESTIONS 1987 ONWARDS IN THE THEORY OF COMPUTATION

 SOLUTIONS TO GATE PROBLEMS
 SOLUTIONS TO GATE PROBLEMS

GATE_1997

THEORY OF COMPUTATION

NOTES AND HINTS ON PROBLEMS

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).

(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.

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