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.

Is PDA non-deterministic?

Definition. A non-deterministic pushdown automaton (NPDA), or just pushdown automaton (PDA) is a variation on the idea of a non-deterministic finite automaton (NDFA). Unlike an NDFA, a PDA is associated with a stack (hence the name pushdown).

Is the above PDA deterministic or nondeterministic?

The above pushdown automaton is deterministic in nature because there is only one move from a state on an input symbol and stack symbol. The non-deterministic pushdown automata can have more than one move from a state on an input symbol and stack symbol.