GATE_1999

THEORY OF COMPUTATION

HINTS AND SOLUTIONS TO PROBLEMS

Q1.6 The sets accepted by pda by final state or empty stack are alternative definitions for the sets accepted and in both cases it is the cfls that are accepted

.

CS6(a) ANSWER----NO

If we choose A to be (0+1)* the B can be any formal language.

QCS6(b) We must check for strings in L1'intersection L2 and L2'intersection L1.

If L1 is contained in L2 then L1 is not contained in the complement of L2. If L1 is contained in L2 then its complement must have string in L2.

CS7. The language is not a cfl. Intersect the language with0*1*c0*1*, the resulting language can be shown not to be a cfl by an application of the pumping lemma.

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