0 votes 0 votes 1. I know that whether a cfg generates regular language is undecidable .... somone plzz help me to prove that whether a given cfl is regular language also undecidable .... 2. how equvilance problem on 2 dcfl is decidable?? Theory of Computation decidability theory-of-computation + – saurabh rai asked Oct 22, 2016 • edited Oct 22, 2016 by saurabh rai saurabh rai 606 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply sudsho commented Oct 23, 2016 reply Follow Share for question 1 refer to this http://cs.stackexchange.com/questions/19482/why-is-deciding-regularity-of-a-context-free-language-undecidable for question 2.....equivalence problem i.e L1=L2 for DCFL or any language except regular is NOT decidable... 0 votes 0 votes saurabh rai commented Oct 23, 2016 reply Follow Share thnx for providing the link will u plzz explain that bcoz i m not able to get that and 2nd problem on dcfl is decidable see the link http://gatecse.in/grammar-decidable-and-undecidable-problems/ 0 votes 0 votes thor commented Nov 16, 2016 reply Follow Share Someone please answer this with proof. 0 votes 0 votes saurabh rai commented Nov 16, 2016 reply Follow Share I think u r getting problem in 2nd. 0 votes 0 votes thor commented Nov 16, 2016 reply Follow Share I have remembered table, but answering why is difficult for me. Please explain first one? 0 votes 0 votes saurabh rai commented Nov 16, 2016 reply Follow Share i think it is not so easy to give proof for above. for 2nd see http://www.lfcs.inf.ed.ac.uk/reports/99/ECS-LFCS-99-411/ECS-LFCS-99-411.pdf 1 votes 1 votes Please log in or register to add a comment.