1994 ANSWERS

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


Animation Calculator Calendar Charts Clocks
Colors Conversions Counters Dates FAQs
Finance Games Health Humour Internet
LiveConnect META Navigation Netscape 4 Others
Password Random Scrolls Search Sound
Validation VRML




SOLUTIONS TO GATE PROBLEMS 
SOLUTIONS TO GATE PROBLEMS 






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 cn|i,n>1} U

{aj bj cm|j,m>1} but the latter cannot.

Q2.10 Answer is 0*1*

Q3.3 ANSWER----TRUE

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 x-block 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) ANSWER----no

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
Go to:
2005,
GATE THEORY OF COMPUTATION

CLICK!!! A remote control for GATE questions and answers!!