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


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^nn>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 {1n01nn>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 bmn.m>1, nm>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 