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

THEORY OF COMPUTATION



PART A

Q3(xiii) Let r = 1(1+0)*, s = 11*0, t = 1*0 be three regular expressions. Which one of the following is true?

(A)L(s) is a subset of L(r) and L(s) is a subset of L(t)

(B) L(r) is a subset of L(s) and L(s) is a subset of L(t)

(C) L(s) is a subset of L(t) and L(s) is a subset of L(r)

(D) L(t) is a subset of L(s) and L(s) is a subset of L(r)

Q3(xiv) Which one of the following is the strongest correct statement about a finite language over some finite alphabet X?

(A) It could be undecidable.

(B) It is Turing machine recognizable

(C) It is a regular language

(D) None of the above

PART B

Q17(a)  Show that Turing machines, which have a read only input tape and a constant work size tape, recognize precisely the class of regular languages.

Q17(b) Let L be the language of all binary strings in which the third symbol from the right is a 1. Give a non-deterministic finite automaton that recognizes L. How many states does the minimised equivalent deterministic finite automaton have? Justify your answer briefly.


 

 

 

 

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