GATE_2001

THEORY OF COMPUTATION

HINTS AND SOLUTIONS TO PROBLEMS

Q1.4 ANSWER----------(A)

S1 is nothing but (00)+, a regular expression and hence denotes a regular set.

S2 is not a regular set as seen from the pumping lemma for regular sets.

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

The union of two cfls is a cfl.

The deterministic and nondeterministic models of the pda are not the same.

The cfls are not closed under intersection or complement.

Q1.6 ANSWER-----(B)

In the worst case we require the entire subset machine in converting a nfa to a dfa.

Q2.5 ANSWER--------------(D)

We have to take the product of a modulo 6 machine and a modulo 8 machine.

Q2.6 ANSWER-------------(D)

L1,L2 and L4 are standard non-regular sets.

L3 is the set (00)*

Q2.7 ANSWER-----------(B)

Just start the turing machine and sit in front of it. If it visits the state q we will know in a finite amount of time else we may never know.

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