CLICK ON A PICTURE BELOW FOR PREVIOUS GATE QUESTIONS 1987 ONWARDS IN THE THEORY OF COMPUTATION


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