CLICK ON A PICTURE BELOW FOR PREVIOUS GATE QUESTIONS 1987 ONWARDS IN THE THEORY OF COMPUTATION
GATE 1989 PROBLEMS
THEORY OF COMPUTATION
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.
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:
PP-----------> preposition 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.