retagged by
8,612 views
32 votes
32 votes

Which one of the following problems is undecidable?

  1. Deciding if a given context-free grammar is ambiguous.
  2. Deciding if a given string is generated by a given context-free grammar.
  3. Deciding if the language generated by a given context-free grammar is empty.
  4. Deciding if the language generated by a given context-free grammar is finite.
retagged by

3 Answers

Best answer
30 votes
30 votes

(A) is the answer. Proving (A) is undecidable is not so easy. But we can easily prove the other three options given here are decidable.

https://gatecse.in/grammar-decidable-and-undecidable-problems/

edited by
3 votes
3 votes

Context free grammar is not closed under ambiguity.A set is closed under an operation means when we operate an element of that set with that operator we get an element from that set. Here, context free grammar generates a context free language and set of all context free languages is also a set. But, ambiguity is not an operation and hence we can never say that CFG is closed under ambiguity. Thus, problem mentioned in option (A) is undecidable.

0 votes
0 votes
A.

CFG is not closed under ambiguity.
Answer:

Related questions

45 votes
45 votes
7 answers
3