1992 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_1992

THEORY OF COMPUTATION

HINTS AND NOTES ON PROBLEMS

 



Q1(xii)ANSWER (B)

(A) seems to be a printing mistake r(*)=r

(B) is a standard identity (r+s)*=(r*s*)*

In (C) rs is present in the left hand side but not in the right hand side regular expression.

In(D) rs is present in the left hand side but not in the right hand side regular expression.

Q1(xviii)ANSWER (C)   

Consider strings of lenght 1 and 2 to find out the correct formula by elimination.

Q1(xix)ANSWER (A) AND (D)

The cfls are closed under union and Kleene closure. A proof with grammars is easy. However they are not closed under complement as {ww|w in(a+b)*} is a csl not cfl but its complement is a cfl. Hence by De Morgan's theorem they are not closed under intersection either.

Q1(xx) ANSWER (A) AND (C)

For the pda the nondeterministic model is more powerful than the deterministic one. {wwR} the language of palidromes is accepted by the former and not the latter.

For the fa and turing machines the nondeterminsitic and deterministic models are equivalent.

Q16.ANSWER (i) AND (ii)

The recursive sets are closed under union and the language of primes in unary is not regular. For the latter we see that the primes cannot be in any arithmetic progression and thus we cannot satisfy the weak form of the pumping lemma for regular sets.

Any formal language is the infinite union of finite singleton sets, one set for each element of the language. Hence infinite union does not preserve the regular sets.

 

 


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