Computer Science Engineering (CSE)

 For operator precedence parsing, which one is true?
  • a)
    For all pair of non-terminal
  • b)
    For all pair of terminals
  • c)
    To delimit the handle
  • d)
    None of the mentioned
Correct answer is option 'A'. Can you explain this answer?

AMAN RAJ answered  •  yesterday
There are two important properties for these operator precedence parsers is that it does not appear on the right side of any production and no production has two adjacent non-terminals. Implying that no production right side is empty or has two adjacent non-terminals. So accordingly to property option (A) is correct.

Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
  • a)
    I and II
  • b)
    I and IV
  • c)
    II and III
  • d)
    II and IV
Correct answer is option 'B'. Can you explain this answer?

Rajkumar answered  •  yesterday
(A) Intersection of two regular languages is regular and checking if a regular language is infinite is decidable.
(B) Deciding regularity of a context free language is undecidable. We check if L(CFG) contains any string with length between n and 2n−1 , where n is the pumping lemma constant. If so, L(CFG) is infinite otherwise it is finite.
(C) Equality problem is undecidable for all languages except in case of finite automata i.e. for regular languages.
(D) We have to check if the grammar obeys the rules of CFG. If, it obeys such rules then it is decidable.  Thus, option (B) is correct. Please comment below if you find anything wrong in the above post.

Fetching relevant content for you