2
$\begingroup$

Is there any known characterization for deterministic pushdown automata (DPDA)? For example, visibly pushdown automata(VPA) is a subclass of DPDA, which is characterized by following syntactic condition: push or pop decision depends on the input symbol. Similarly, is there any either syntactic or semantic condition, which when satisfied by a given non-deterministic PDA, guarantees its determinizability?

$\endgroup$
  • 2
    $\begingroup$ Deterministic push-down automata are already defined by a syntactic condition. So what is the question? $\endgroup$ – Emil Jeřábek Aug 1 '18 at 14:20
  • $\begingroup$ Well. Let me explain my question better. Let $A$ be given non-deterministic PDA. Does there exist an equivalent deterministic PDA? I think this question is undecidable in general. Is there any other condition (e.g input driven stack operations for VPA) known, which when satisfied by $A$ guarantees that $A$ can be made deterministic? Does undecidability of determinizability checking imply no such condition can ever exist? $\endgroup$ – Devendra Bhave Aug 1 '18 at 17:10
  • $\begingroup$ Ok, this makes sense. You should include this explanation in the question itself (comments are not meant to be permanent). $\endgroup$ – Emil Jeřábek Aug 2 '18 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.