1991 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_1991

THEORY OF COMPUTATION

HINTS AND NOTES ON SOLUTIONS



Q3(xiii)ANSWER--------(A) and (C)

From an examination of the three regular expressions t contains a 0 wheras the other two do not. So L(t) cannot be a subset of the other two sets. This excludes (D).

L(r) contains 100 wheras the other two do not. So L(r) cannot be a subset of the other two. This excludes (B).

Note that (A) and (C) are the same.

Q3(xiv) ANSWER------(D)

The regular sets are the smallest class that contain all the finite sets.

Q17(a) If we take a turing machine and take away its ink it becomes a 2DFA or 2NFA. We have the standard theorem that these accept only the regular sets.

Q17(b) The nfa for the machine over {0,1} is given below:

  input 0 input 1
(start state) H H H,P
P M M
M *C *C
*C ---------------------------- --------------------------

The equivalent minimal dfa has 8 states as can be shown by constructing the dfa and minimising it. This is the example of a nfa to dfa conversion which requires an exponential number of states.



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!!