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


GATE 1994 PROBLEMS
THEORY OF COMPUTATION
SECTION A
Q1.16 Which of the following conversions is not possible (algorithmically)?
(A) Regular grammar to contextfree grammar
(B) Nondeterministic FSA to deterministic FSA
(C) Nondeterministic PDA to deterministic PDA
(D) Nondeterministic Turing machine to deterministic Turing machine
Q2.10 The regular expression for the language recognized by the finite state automaton in the figure below is 
Q3.3 State True or False with one line explanation:
A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).
SECTION B
Q19(a) Given a set S = {x  there is an xblock of 5's in the decimal expansion of pi}
(note: xblock is a maximal block of x successive 5's)
Which of the following statements is true with respect to S?
(i) S is regular
(ii) S is recursively enumerable
(iii) S is not recursively enumerable
(iv) S is recursive
Q19(b) Given that a language L1 is regular and that the language L1 U L2 is regular, is te language L2 always regular? Prove your answer.
Q20. A grammar G is in ChomskyNormal form(CNF) if all its productions are of the form A>BC or A>a, where A,B and C are nonterminals and a is a terminal. Suppose G is a CFG in CNF and w is a string i L(G) of length l. How long is a derivation w in G?
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 