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


GATE 1997 PROBLEMS
THEORY OF COMPUTATION
SECTION A
Q3.4 Give X={a,b}, which of the following sets is not countable?
(A) Set of all strings over X
(B) Set of all languages over X
(C) Set of all regular languages over X
(D) Set of all languages over X accepted by Turing machines
Q6.4 Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?
(A) 0*(1+0)* (B)0*1010* (C) 0*1*01 (D) 0*(10+1)*
Q6.5 Which one of the following is not decidable?
(A) Given a turing machine M, a string s and an integer k, M accepts s within k steps
(B) Equivalence of two given turing machines
(C) Language accepted by a given finite state machine is nonempty.
(D) Language generated by a contextfree grammar is nonempty.
Q6.6 Which of the following languages over {a,b,c} is accepted by a deterministic push down automaton?
(A) {wcwR w in(1+b)*}
(B) {wwRw in {a,b,c}*}
(C){a^n b^n c^nn>=0}
(D) { w w is a palidrome over {a,b,c}
Note: wR is obtained by reversing the string "w".
Q11. Consider the grammar
S>bSe
S>PQR
P>bPc
P>epsilon
Q>cQd
Q>epsilon
R>dRe
R>epsilon
where S,P,Q,R are nonterminals with S being the start symbol; bc,c,d,e are terminal symbols and "epsilon" is the empty string. This grammar generates strings of the form b^i c^j d^k e^m for some i, j,k, m <=0.
(a) what is the condition on the values of u, j, k ,m?
(b) Find the smallest string that has two parse trees.
SECTION B
Q20. Construct a finite state machine with minimum number of states, accepting all strings over {a,b} such that the number of a's is divisible by two and the number of b's is divisible by three.
Q21. Given that L is a language accepted by a finite state machine, show that Lp and Lr are accepted by some finite state machines where
Lp ={sss"in L for some string s"},
Lr={ss obtained by reversing some string in L}
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 