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


GATE_1989
THEORY OF COMPUTATION
HINTS AND SOLUTIONS
PART A
Q3(ii) ANSWER(A) AND (C)
The regular sets and cfs are closed under the operations of union and concatenation.
The operations of intersection and complementation preserve the regular sets as seen from the definition and properties of extended regular expressions.
However the cfls are not closed under complementation or intersection. The language {www in (a+b)*} is a csl that is not a cfl but its complement is a cfl. The language {an bn cnn>1} is a cls that is not a cfl but its complement is a cfl. The intersection of the two cfls {an bn cii,n>1} and {aj bm cmj,m>1} is the standard csl {an bn cnn>1}.
Q3(III)ANSWER(B) AND (D)
The membership problem for cfls is decidable, we have the CYK algorithms or we have general parsing algorithms for cfls.
The halting problem of fa is decidable trivially.
It is undecidable if a given cfg is regular, or whether a turing machine accepts a particular string.
PART B
Q15(a)ANSWERNO
Any formal language is the union(possibly infinite) of each of its elements treated as a singleton set. So the infinite union of regular sets need not be regular.
Q15(b) ANSWERCEIL(LOG2(L))+1
If we have l as a power of 2 then the derivation tree with the leaves removed is a complete binary tree of height log2(l). For the leaves to be generated we add 1 to the height. In general l will be between two powers of two so we take the ceil of log2(l).
Q15(c) The sentence is "Ram sold the pen to Hari"
The leftmost derivation is given below:
S>NP VP
>NP1 VP
> noun VP
>Ram VP
>Ram verb NP PP
>Ram sold NP PP
> Ram sold article NP PP
>Ram sold the NP PP
> Ram sold the pen PP
You can build the derivation tree from the above leftmost derivation.
> Ram sold the pen preposition NP
> Ram sold the pen to NP
> Ram sold the pen to NP1
>Ram sold the pen to noun
>Ram sold the pen to Hari
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 