1989 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_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 {ww|w in (a+b)*} is a csl that is not a cfl but its complement is a cfl. The language {an bn cn|n>1} is a cls that is not a cfl but its complement is a cfl. The intersection of the two cfls {an bn ci|i,n>1} and {aj bm cm|j,m>1} is the standard csl {an bn cn|n>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)ANSWER-----NO

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) ANSWER---CEIL(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
Go to:
2005,
GATE THEORY OF COMPUTATION

CLICK!!! A remote control for GATE questions and answers!!