GATE 1990 PROBLEMS

THEORY OF COMPUTATION

PART A

Q3(iv) Recursive languages are:

(A) a proper subset of context-free languages.

(B) always recognisable by pushdown automata

(C) also called Type 0 languages.

(D) recognisable by Turing machines.

Q3(vii) It is undecidable whether:

(A) an arbitrary Turing machine halts after 10*phi steps.

(B) a Turing machine prints a specific letter.

(D) a Turing machine computes the product of two numbers.

Note:- Choice (C) is absent in the question paper copy available to me.

PART B

Q15(a) Is the language generated by the grammar G regular? If so, give a regular expression for it, else prove otherwise.

G: S------------->aB

    B-------------->bC

   C------------->xB

   C---------->c

Q15(b) Complete the following production rules which generate the language

L = { a^n b^n c^n | a, b, c in Ê }

where variables R and Q are used to move back and forth over the current string generated

A----------->aYc

Y------------>aYc|Q

Qc---------->Rc

cR--------->Rc

aR--------->a_Q

bR---------->b_Q

Qb--------->_ _ _
Qc---------->cQ

Q_---------->R' c

cR' ----------> _ _ _

bR' ----------> _ _ _
a R'----------->a _ _

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