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


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