Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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
