1998 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_1998

THEORY OF COMPUTATION

HINTS AND SOLUTIONS TO PROBLEMS



Q1.9 ANSWER-----------(D)

Note the regular expression identity (r+s)*=(r*s*)*. With t=01 and s=1 it is seen that both the regular expressios are the same.

Q1.10ANSWER-------------(A)

(A) The squares written in binary are 1,10,100,1000,----etc. The finite automata has merely got to recognise a 1 followed by any number of 0's.

(B) The set {0^2^n|n>1} cannot be a regular set as shown by the weak form of the pumping lemma for regular sets. The squares cannot be in any arithmetic progression.

(C) The strings with an equal number of 0's and 1's is a standard language which is a cfl and not a regular set.

(D) But for the first element the set is {1n01n|n>1} which cannot be regular as is seen from the pumping lemma for regular sets.

Q1.11 ANSWER-------------(B) AND (C)

The deterministic and nondeterministic models of the pushdown automata are not the same.

The deterministic and nondeterministic models of finite auomata are the same and the same statement holds for turing machines.

Q1.12 ANSWER--(C) AND (D)

In C after a 11 we will have a 00 only. The 0's occur in pairs.

In D the 1's occur in pairs and an odd number of 1's are not possible.

 

Q2.6 ANSWER-----------(B)

 The subsets of the regular set (0+1)* are all the formal languages and hence not all regular.

In the choices  (A) and (C) we have finite sets which are automatically regular.

In (D) we have the fact that the regular sets are closed under intersection.

Q3(b) (1^k 0 1^k)+

Q4. This is the modulo 5 machine.

  input:0 input:1
q0 q0 q1
q1 q2 q3
q2 q4 q0
q3 q1 q2
q4 q3 q4

Q13. Let

R1=f(q0,1,Z0)={(q0,XZ0)}

R2=f(q1,e,Z0)={(q0,e)}

R3=f(q0,1,X)={(q0,XX)}

R4=f(q1,1,X)={(q1,e)}

R5=f(q0,0,X)={(q1,X)}

R6=f(q1,0,X0)={(q0,Z0)}

1. R1,R2 and R3 consume n>1 number of 1's and push an equal number of X's onto the pushdown store with the state remaining the same as q0.

2. R5 rejects a single 0 and the pda makes a transition to the state q1.

3.  In R4 we consume n number of 1's and pop an equal number of X's from the stack with the PDA ending up in state q1.

4. In R6, one more 0 is rejected, and the PDA ends up in state q0.

5. R2 allows the stack to be emptied allowing the PDA to accept

The language accepted by empty stack is L={1^n 0 1^n 0| n > 1} 

Q14(a). The first choice of   productions gives S---------->* an A bn

or S--------------------->*am B bm

A generates a+ and B generates b+

So the set generated is  L={an bm|n.m>1, |n-m|>1]

Q14(b). The new grammar is

P1: S1--------------->aS1 ba S1b

P2: S1------------------>aAb

P3:A------------------------>aAb

P4:A----------------->ab

P5: S1-------------->aBb

P6:B-------------->aBb

P7:B----------->ab

The rules P1,P2,P4, P6 and P7 have been added.

QCS14(c) The language is not inherently ambiguous. We can construct a dpda which will initially push all the a's unstack with the next set of b's.Then it  will stack the a's and pop with the trailing b's. So the language is a DCFLand DCFLs are not inherent ambiguous as we can construct LR(0) unambiguous grammars for them.


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