1992 QUESTIONS

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 PROBLEMS

THEORY OF COMPUTATION



PART A

Q2(xii) Which of the following regular expression identities are true?

(A) r(*) = r*

(B) (r*S*)* = (r + s)*

(C) (r + s)* = r* + s*

(D) r*s* = r* + s*

 

Q2(xviii) If G is a context-free grammar and w is a string of length l in L(G), how long is a derivation of w in G, if G is in the Chomky normal form?

(A)  2l       (B) 2l + 1     (C) 2l - 1         (D) l

Q2(xix) Context-free languages are

(A) closed under union                                        (B) closed under complementation

(C) closed under intersection                                (D) closed under Kleene closure

Q2(xx) In which of the cases stated below is the following statement true?

"For every nondeterministic machine M1 there exists an equivalent deterministic machine M2 recognizing the same language".

(A) M1 in a nondeterministic finite automaton.

(B) M1 is a nondeterministic PDA

(C) M1 is a nondeterministic Turing machine

(D) For no machine M1 is the above statement True

PART B

Q16 Which of the following three statements are true? Prove your answer.

(i) The union of two recursive languages is recursive.

(ii) The language {0^n | n is a prime } is not regular.

(iii) Regular languages are closed under infinite union.


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