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


GATE 2001 PROBLEMS
THEORY OF COMPUTATION
SECTION A
CS 1.4 Consider the following two statements:
S1: {0^2nn>=1} is a regular language.
S2: {0^m1^n0^(m+n)m>=1 and n>=1} is a regular language
Which of the following statements is correct?
A. Only S1 is correct
B. Only S2 is correct
C. Both S1 and S2 are correct
D. None of S1 and S2 is correct
CS1.5 Which of the following statements is true?
A. If a language is context free it can always be accepted by a deterministic pushdown automaton.
B. The union of two context free languages is context free
C. The intersection of two context free languages is context free
D. The complement of a context free language is context free
CS1.6 Given an arbitrary nondeterministic finite automaton(NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
A. N^2
B. 2^N
C.2N
D. N!
CS2.5 Consider a DFA over X= {a,b} accepting all strings which have number of a's divisible by 6 and the number of b's divisible by 8. What is the minimum number of states that the DFA will have?
A. 8
B. 14
C. 15
D. 48
CS2.6 Consider the following languages:
L1 = {www in {q,b}*}
L2 = {wwR w in {a,b}*, wR is the reverse of w}
:3 = { 0^2ii is an integer}
L4 = {0^i^2 i is an integer}
Which of the following languages are regular?
A. Only L1 and L2
B. Only L2, L3 and L4
Only L3 and L4
D. Only L3
CS2.7 Consider the following problem X.
Given a Turing machine M over the input alphabet X, any state q of M and a word w in X*, doe sthe computatio9n of M on w visit the state q?
Which of the following statements about X is correct?
A. X is decidable
B. X is undecidable but partially decidable
C. X is undecidable and not even partially decidable.
D. X is not a decision problem.
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 