1989 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 1989 PROBLEMS

THEORY OF COMPUTATION



PART A

Q3(ii) Context-free languages and regular languages are both closed under the operation(s) of:

(A) Union                    (B)  Intersection

(C) Concatenation        (D) Complementation

Q3(iii) Which of the following problems are undecidable?:

(A)  Membership problem in context-free languages.

(B)  Whether a given context-free language is regular.

(C)  Whether a finite state automation halts on all inputs.

(D)  Membership problem for type 0 languages.

PART B

Q15(a) Is the class of regular sets closed under infinite union? Explain.

(b) What is the minimum height of the parse tree of a string of length in a language L whose grammar is in the Chomky-Normal form? Explain.

(c) Consider a context-free grammar with the following production rules:

S-------->NP  VP

NP--------->article NP1

NP--------->NP1

NP1--------->noun

PP-----------> preposition NP

NP----------> verb

VP--------->verb NP

VP----------->verb NP PP

The following sentence is to be parsed using the above grammar.

Ram sold the pen to Hari. Categories of terminal symbols are as given below:

Ram    :    noun

Sold    :    verb

the    :       article

pen    :     noun

to     :        preposition

Hari   :     noun

Obtain a parse-tree for the given sentence.

 


 

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!!