UTpaper

Free mock tests & test series

Question 85Asked in UGC NET Computer Science, November 2017 (Paper II & III, Selected Questions)

Which of the following problem is undividable?

  1. ATo determine if two finite automata are equivalent
  2. BMembership problem for context free equivalent
  3. CFiniteness problem for finite automata
  4. DAmbiguity problem for context free grammar
Show answerHide answer

Correct answer: (D) Ambiguity problem for context free grammar

Explanation

The ambiguity problem for context-free grammars is undecidable: no Turing machine can always halt and decide whether an arbitrary CFG is ambiguous. Equivalence of finite automata, CFG membership and finiteness for finite automata are decidable.

From UGC NET Computer Science PYQ, November 2017 (Paper II & III, Selected Questions)

This is question 85 of UGC NET Computer Science PYQ, November 2017 (Paper II & III, Selected Questions). See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.