GATE 1995 PROBLEMS

THEORY OF COMPUTATION

SECTION A

Q1.10 Consider a grammar with the following productions

S----->aAb|bAc|aB

S--->AS|b

S----->Abb|ab

bA-------->bdb|b

The above grammar is

(a) context-free      (b) regular        (c) context-sensitive         (d) LR(k)

Q2.20 Which of the following definitions below generates the same language as L, where L = {x^n y^n|n>=1}?

I. E----->xEy|xy        II.xy|(x+xyy+)            III.x+y+

(a) I only        (b) I and II         (c) II and III            (d) II only

Q2.24 Let X={0,1}, L=X* and R={0^n 1^n such that n > 0} then the languages LUR and R are respectively

(a) Regular, Regular                (b) Not Regular, Regular

(c) Regular, Not Regular        (d) Not Regular, Not Regular

SECTION B

Q11. Let L be a language ove X i.e. L is a subset of X*. Suppose L satisfies the two conditions given belwo

(i) L is in NP and

(ii) For every n, there is exactly one string of length n that belongs to L.

Let Lc be the complement of L ove X* and show that Lc is also in NP.

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