1999 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 1999 PROBLEMS

THEORY OF COMPUTATION



SECTION A

Q1.4 Consider the regular expression (0+1)(0+1).....n times. The minimum state finite automaton that recognizes the language represented by this regular expression contains

(A) n states                (B) n+1 states

(C) n+2 states            (D) None of the above

Q1.5 Context-free languages are closed under:

(A) Union, intersection

(B) Union, Kleene closure

(C) Intersection, complement

(D) Complement, Kleene closure

Q1.6 Let Ld be the set of all languages accepted by a PDA by final state and Le be the set of all  languages accepted by empty stack. Which of the following is true?

(A) Ld = Le

(B) Ld is a superset of Le

(C) Ld is  a subset of Le

(D) None of the abovE

SECTION B

CS6 (a) Given that A is regular and (AUB) is regular, does it follow that B is necessarily regular? Justify your answer.

(b) Given two finite automata M1, M2 outline an algorithm to decide if L(M1) is a strict subset of L(M2).

CS7. Show that the language L = {xcx|x in {0,1}* and c is a terminal symbol} is not context free, with c not the same as o or 1.


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