2 votes 2 votes G1 and G2 are DCFL. Is G1 = G2 Decidable or Undecidable? Naveen K Verma asked Jan 16, 2018 Naveen K Verma 478 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply MiNiPanda commented Jan 16, 2018 reply Follow Share Decidable though you may find places where they give '?' mark in the table.. I recently got to know it is decidable. 1 votes 1 votes gauravkc commented Jan 16, 2018 reply Follow Share Geraud Senizergues (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,[4] a proof that earned him the 2002 Gödel Prize. For nondeterministic PDA, equivalence is undecidable. Reference : https://en.wikipedia.org/wiki/Deterministic_pushdown_automaton#Equivalence_problem 1 votes 1 votes MiNiPanda commented Jan 16, 2018 reply Follow Share Was about to post the screenshot :p 1 votes 1 votes Naveen K Verma commented Jan 16, 2018 reply Follow Share thanks :-) 0 votes 0 votes Please log in or register to add a comment.