<p>Is the following problem decidable?
If so, what's the best algorithm known?</p>
<blockquote>
<p><strong>Instance:</strong> a deterministic pushdown automaton <span class="math-container">$A$</span><br />
<strong>Question:</strong> Does there exist (i) some partition of the alphabet into push, pop, and level symbols and (ii) a visibly pushdown automaton that recognizes the language accepted by <span class="math-container">$A$</span>?</p>
</blockquote>

CC BY-SA 4.0
2020-12-25T18:28:16.187Z
Due to the decidability of DPDA equivalence one 'merely' has to show there exist *some* (no matter how bad) computable function $f(n)$ upper-bounding the sufficient size of a VPDA for $L(A)$ given DPDA $A$ of size $n$, as we can then simply enumerate them.
orlp
CC BY-SA 4.0
2020-12-25T18:33:53.333Z
And regardless this immediately shows the problem is at least semi-decidable.
orlp
<fl.formal-languages><automata-theory><context-free>
Deciding whether DCFG is visibly pushdown
Antimony
# Deciding whether DCFG is visibly pushdown

(Asked by: username_0 on 2020-12-24)

Is the following problem decidable?
If so, what's the best algorithm known?

> **Instance:** a deterministic pushdown automaton $A$  
> **Question:** Does there exist (i) some partition of the alphabet into push, pop, and level symbols and (ii) a visibly pushdown automaton that recognizes the language accepted by $A$?

**Tags:** fl.formal-languages, automata-theory, context-free

> **Comments:**
> **username_1**: Due to the decidability of DPDA equivalence one 'merely' has to show there exist *some* (no matter how bad) computable function $f(n)$ upper-bounding the sufficient size of a VPDA for $L(A)$ given DPDA $A$ of size $n$, as we can then simply enumerate them.  
> **username_1**: And regardless this immediately shows the problem is at least semi-decidable.  

---

## 0 answers

