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