2,019 views

3 Answers

Best answer
3 votes
3 votes

Both the Problems are Trivially Decidable. We know that Every CFG (Doesn't matter whether it is ambiguous or unambiguous ) generates a CFL . So, If someone comes to you and asks you "$G$ is a CFG, Will $L(G)$ be CFL ??" ..You can just trivially say "Yes". 

Or another way to understand it is as following :

Decidable problems mean that there is Some Algorithm to solve them (Though Algorithm word is not precisely defined but I am assuming the same meaning of this word as you know it)..So, This Problem is decidable because I can write an Algorithm for this Problem... My Algorithm will take whatever CFG $G$ you pass as input and Will (without calculating/doing anything) just simply output "Yes". $O(1)$ time algorithm(vacuous algorithm).. 


When the Domain is Unrestricted grammars i.e. $G$ can be any Type-0 grammar and then if it is asked "whether $L(G)$ is CFL or not" ....is Undecidable (Because of Rice's theorem)

selected by
0 votes
0 votes

it is better to learn this table for gate exam becz many question are direct regarding closure nd decidability.

ist one is membership hence fromtable it is decidable

2nd one is ambiguity of grammar which is undecidable

0 votes
0 votes
Remember here its mentioned L(G) i.e. language of the context free grammar, so that’s why its decidable.

But lets say it mentions “whether any language L is CFL or not? ”. Then it will be undecidable.

Related questions

2 votes
2 votes
1 answer
1
Na462 asked Sep 2, 2018
785 views
3 votes
3 votes
1 answer
3
Utkarsh Anand asked Jul 31, 2017
1,360 views
Are Turing decidable languages are closed under Complementation, Reversal, Homomorphism, Inverse Homomorphism and Substitution?