0 votes 0 votes Ans. B Theory of Computation decidability theory-of-computation recursive-and-recursively-enumerable-languages + – Na462 asked Sep 2, 2018 Na462 405 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Na462 commented Sep 2, 2018 reply Follow Share I understand DPDA as DCFL. My doubt is why Option B is true because say L1,L2 are two DPDA, and we need to prove :- L1 = L2 -----> (L1 - L2) U (L2 - L1) = Phie ------> (L1 intersection L2 ') U (L2 intersection L1 ') = Phie DCFL are closed in Complementation but not in intersection as well as union SO HOW THIS IS DECIDABLE ?? 0 votes 0 votes MiNiPanda commented Sep 2, 2018 reply Follow Share If you are interested to know how equality of 2 DCFLs is a decidable problem then I am giving you the link of the research paper of the man who got Godel prize for this proof http://sci-hub.tw/10.1007/3-540-63165-8_221 I guess after visiting it you won't have the interest to know any further :v :P (kidding :P) 1 votes 1 votes srestha commented Sep 2, 2018 reply Follow Share @MiniPanda really? :p @Na462 is it not undecidable? https://gateoverflow.in/96057/toc-dcfl-closed-under-equivalence-property 0 votes 0 votes Gurdeep Saini commented Oct 18, 2018 reply Follow Share equivalence in DFA is decidable equivalence in DPDA is decidable equivalence in PDA is undecidable so B is answer 0 votes 0 votes Please log in or register to add a comment.
