<p>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?</p>

CC BY-SA 4.0
2018-08-01T14:20:16.500Z
Deterministic push-down automata are already *defined* by a syntactic condition. So what is the question?
Emil Jeřábek
CC BY-SA 4.0
2018-08-01T17:10:55.133Z
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?
Devendra Bhave
CC BY-SA 4.0
2018-08-02T09:57:43.800Z
Ok, this makes sense. You should include this explanation in the question itself (comments are not meant to be permanent).
Emil Jeřábek
<automata-theory>
Characterization of deterministic pushdown automata
Devendra Bhave
# Characterization of deterministic pushdown automata

(Asked by: username_0 on 2018-08-01)

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?

**Tags:** automata-theory

> **Comments:**
> **username_1**: Deterministic push-down automata are already *defined* by a syntactic condition. So what is the question?  
> **username_0**: 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?  
> **username_1**: Ok, this makes sense. You should include this explanation in the question itself (comments are not meant to be permanent).  

---

## 0 answers

