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.

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