1 votes 1 votes Is the following problem decidable-: 1. Given a deterministic context-free grammar G, is L(G) = Σ* for some alphabet Σ ? Please also provide explaination. Theory of Computation decidability theory-of-computation + – Aakanchha asked Jan 26, 2018 Aakanchha 913 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments sumit chakraborty commented Jan 26, 2018 reply Follow Share It is decidable. Check this : https://gatecse.in/grammar-decidable-and-undecidable-problems/ . Not much of an explanation but a good way to start. 0 votes 0 votes Aakanchha commented Jan 26, 2018 reply Follow Share @sumit thanku 0 votes 0 votes Prateek Raghuvanshi commented Jan 7, 2019 reply Follow Share because DCFL closed under complement that's why we can say that DCFL closed under completeness problem. 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes the COMPLETENESS problem for DCFG and CFG is always undecidable suryaprakash answered Jun 1, 2018 suryaprakash comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes It is decidable. Since DCFLs are closed under complementation,find if L’(L complement) = empty language. If L’ is empty then L is complete or L(G) = Σ* . Abhipsa Panda answered May 24, 2022 Abhipsa Panda comment Share Follow See all 0 reply Please log in or register to add a comment.
for some alphabet Σ 
?
