2 votes 2 votes Equality of two DPDA is decidable or undecidable ? Theory of Computation theory-of-computation decidability + – dragonball asked Dec 20, 2017 dragonball 1.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply Arjun commented Dec 20, 2017 reply Follow Share https://gateoverflow.in/96057/toc-dcfl-closed-under-equivalence-property 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes It is decidable Géraud Sénizergues (1997) proved that the equivalence problem for deterministic PDA (i.e. given two deterministic PDA A and B, is L(A)=L(B)?) is decidable,a proof that earned him the 2002 Gödel Prize. For nondeterministic PDA, equivalence is undecidable. Obafgkme answered Sep 26, 2019 Obafgkme comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes always UNDECIDABLE suryaprakash answered Jun 1, 2018 • edited Jun 1, 2018 by suryaprakash suryaprakash comment Share Follow See 1 comment See all 1 1 comment reply Obafgkme commented Sep 17, 2019 reply Follow Share Nope, it is decidable Géraud Sénizergues (1997) proved that the equivalence problem for deterministic PDA (i.e. given two deterministic PDA A and B, is L(A)=L(B)?) is decidable,a proof that earned him the 2002 Gödel Prize. For nondeterministic PDA, equivalence is undecidable. 0 votes 0 votes Please log in or register to add a comment.
