Undecidability

Question 1

Which one of the following problems is undecidable?

A
Deciding if a given context-free grammar is ambiguous.
B
Deciding if a given string is generated by a given context-free grammar.
C
Deciding if the language generated by a given context-free grammar is empty.
D
Deciding if the language generated by a given context-free grammar is finite.
Theory-of-ComputationUndecidabilityGATE 2014 [Set-3]Video-Explanation
Question 1 Explanation: 
The problem, whether a given CFG is ambiguous is undecidable, as we don’t have any algorithm which decides it.
We have a membership algorithm which decides that whether a given string is generated by a given context-free grammar. Similarly, the problems, whether the language generated by a given context-free grammar is empty and the language generated by a given context-free grammar is finite are decidable.
There is 1 question to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access