<p>Eryk Kopczyński[1] showed in 2015 that separability (that's the name of your problem) of visibly pushdown languages by regular languages is undecidable.  The class of visibly pushdown languages is a strict subset of deterministic CFL. </p>

<p>[1]:    Eryk Kopczyński, Invisible Pushdown Languages, LICS'16, available at <a href="https://arxiv.org/abs/1511.00289" rel="noreferrer">https://arxiv.org/abs/1511.00289</a></p>

CC BY-SA 3.0
2017-12-16T10:38:39.010Z
2017-12-16T14:05:59.147Z
2017-12-16T14:05:59.147Z
Michaël Cadilhac
<p>Suppose you are given two <em>deterministic</em> push down automata which recognize languages $A$ and $B$, and wish to determine whether there is a regular language $R$ such that $A \subseteq R$ and $R \cap B = \emptyset$. Basically, the challenge is to determine whether there is a DFA that can recognize which of the two languages any given string comes from, given that it comes from one of those languages.</p>

<p>Is this decideable? If so, what is the complexity? Can the DFA be constructed explicitly?</p>

<automata-theory>
Regular language that discriminates between two deterministic CFGs
Antimony
# Regular language that discriminates between two deterministic CFGs

(Asked by: username_0 on 2017-12-16)

Suppose you are given two *deterministic* push down automata which recognize languages $A$ and $B$, and wish to determine whether there is a regular language $R$ such that $A \subseteq R$ and $R \cap B = \emptyset$. Basically, the challenge is to determine whether there is a DFA that can recognize which of the two languages any given string comes from, given that it comes from one of those languages.

Is this decideable? If so, what is the complexity? Can the DFA be constructed explicitly?

**Tags:** automata-theory

---

## 1 answers

### Answer by username_1 on 2017-12-16. Score: 15 | Accepted answer

Eryk Kopczyński[1] showed in 2015 that separability (that's the name of your problem) of visibly pushdown languages by regular languages is undecidable. The class of visibly pushdown languages is a strict subset of deterministic CFL.

[1]: Eryk Kopczyński, Invisible Pushdown Languages, LICS'16, available at <https://arxiv.org/abs/1511.00289>


---

