2000 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_2000

THEORY OF COMPUTATION

HINTS AND SOLUTIONS TO PROBLEMS



 

Q1.4 ANSWER-----------(C)

(a+b*) is the same as (a+b+b*)=(a+b)*

Q1.5 ANSWER--------(B)

L is (00)+ as the 0's always occur in pairs.

(D) is not correct as the grammar is a cfg.

(A) is excluded as 00 is in the language generated.

Q2.9 ANSWER-----------(A)

For P1 simply trace the path through the state diagram of the finite automata.

For P2 take the reduced grammar in the CNF and draw the graph of the grammar. If cycles exist the cfl is infinite else it is finite.

Q.CS7(a). The finite automat state transition diagram is given below.

  input: 0 input:1
*q0 Reject q1
*q1 q0 Reject
Reject Recject Reject

By examination we find all the states can be distinguished on some input string. So the minimal automata is the same as that given above.

Q3.7(b)By examination it seen that the first production will demand the same number of b's as a's.A can optionally yield extra b's. So we have j>i as the required condition.

Q.CS8.(a) q0 is a push state which pushes 0's and 1's onto the stack. So we have

del(q0,2,s)=(q0,2.s)

q1 is a pop state so we have

del(q1,2,2.s)=(q1,s)

QCS8(b) q0 and q1 will be push states where for every 0 in the input we nondeterministially push one or two 0's onto the stack.

del(q0,0,s)={(q0,0.s),(q2,0.s)}

del(q2,e,s)={(q0,0.s)}

When a 1 occurs we nondeterministically unstack one or two 0's from the stack.

del(q0,1,0.s)={(q1,s)}

del(q0,e,s)={(q1,s)}

In q1 the pop state we unstack one or two 0's for a 1 in the input.

del(q1,1,0.s)={(q1,s),(q2,s)}

del(q2,1,0.s)={(q1,s)}


 

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