1990 QUESTIONS

CLICK ON A PICTURE BELOW FOR PREVIOUS GATE QUESTIONS 1987 ONWARDS IN THE THEORY OF COMPUTATION


Animation Calculator Calendar Charts Clocks
Colors Conversions Counters Dates FAQs
Finance Games Health Humour Internet
LiveConnect META Navigation Netscape 4 Others
Password Random Scrolls Search Sound
Validation VRML




SOLUTIONS TO GATE PROBLEMS 
SOLUTIONS TO GATE PROBLEMS 






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

CLICK!!! A remote control for GATE questions and answers!!