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

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.