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


GATE 2000 PROBLEMS
THEORY OF COMPUTATION
SECTION A
Q(1.4) Let S and T be languages over X={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
A. S is a proper subset of T
B. T is a proper subset of S
C. S = T
D. S intersection T = empty set
Q(1.5) Let L denote the language generated by the grammar S>0S000. Which of the following is true?
A. L = 0+
B. L is regular but not 0+
C. L is context free but not regular
D. L is not contextfree
Q(2.8) What can be said about a regular language L over {a} whose minimal finite state automaton has two states?
A. L must be {a^nn is odd}
B. L must be {a^n n is even}
C. L must be {a^nn>= 0}
D. Eother L must be {a^nn is odd}, or L must be {a^nn is even}
Q(2.9) Consider the following decision problems:
(P1) Does a given finite state machine accept a given string.
(P2) Does a given context free grammar generate an infinite number of strings.
Which of the following is true?
A. Both (P1) and (P2) are decidable.
B.Neither (P1) nor (P2) is decidable
C. Only (P1) is decidable
D. Only (P2) is decidable
SECTION B
CS7 (a) Construct a minimal finite state machine that accepts the language over{0,1}, of all strings that contain neither the substring 00 nor the substrng 11.
CS7(b) Consider the grammar
S>aSAb
S>e
A>bA
A>e
where S, A are nonterminal symbols with S being the start symbol; a, b are terminal symbols and e is the empty string. This grammar generates strings of the form a^ib^j for some i,j>=0, where i and j satisfy some condition. What is the condition on the values of i and j?
CS8. A push down automaton (pda) is given in the following extended notation of finite state diagrams:
The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the for d, s/s' where d is the ilnput symbol read and s, s' are the stack contents before and after the move. For example, the edge labeled , s/1.s denotes the move from state q0 to q0 in which the input symbol 1 is read and pushed to the stack.
(a) Introduce two edges with appropriate labels in the above diagram so that the resulting pda accepts thelanguage
{x2xRx in {0,1}*, xR denotes reverse of x},
by empty stack
(b) Describe a nondeterministic pda with three states in the above notation that accepts the language {0^n1^mn <= m <= 2n} by empty stack.
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 