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