2,762 views

1 Answer

Best answer
15 votes
15 votes
See, firstly DCFLs are closed under complementation. So this is how we decide:

Given a language L, take its complement L' and check if L' is empty => L is complete.

Although emptiness is decidable for both DCFLs and CFLs, however CFLs are not closed under complementation. Hence, decidable in case of DCFLs. For CFLs we have to look for a different approach which actually doesn't exist (requires another proof) and hence the problem becomes undecidable.
selected by

Related questions

0 votes
0 votes
0 answers
1
Mk Utkarsh asked Sep 15, 2018
552 views
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL
0 votes
0 votes
1 answer
3
daksirp asked Jul 9, 2018
670 views
Soutce : https://gatecse.in/grammar-decidable-and-undecidable-problems/Why L(G1) ⋂ L(G2) = Φ ?? is undecidable for dcfl, cfl etc ?? please explain it anyone
0 votes
0 votes
1 answer
4
Sanjay Sharma asked Jul 3, 2016
4,731 views
Which of the following problem is undecidableMembership problem for CFLMembership problem for CSLMembership problem for regular setMembership problem for type 0 languages...