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


GATE_1994
THEORY OF COMPUTATION
HINTS AND SOLUTIONS TO PROBLEMS
Q1.16 ANSWER (A) AND (B)
A regular grammar is trivially a context free grammar.
There are algorithms to convert nfa and nondeterministic turing machines to deterministic machines accepting the same set. For finite automata it is the subset machine. For turing machines we number the moves and generate ordered sequences of integers and map the same to the moves.
The nondeterminsitic pda is more powerful than a deterministic one. The former can accept {ai bn cni,n>1} U
{aj bj cmj,m>1} but the latter cannot.
Q2.10 Answer is 0*1*
Q3.3 ANSWERTRUE
A full adder is nothing but a finite automata. It however depends on how we encode the problem. For example the set {0n 1m 0m+n m,n>1} is not regular.
Q19(a) ANSWER (ii)
We just run a turing machine designed to compute pi to better and better approximations. If it happens to yield a xblock of 5's we stop.
(i) is excluded as a fa cannot count.
We cannot guarentee an algorithm at present and so this excludes S.
Q19(b) ANSWERno
Let L1 be the regular set (0+1)* and L2 any formal language(not necessaily regular). Then the union is always regular.
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 