Reguläre Sprache, die zwischen zwei deterministischen CFGs unterscheidet

Angenommen, Sie erhalten zwei deterministische Push-down-Automaten, die die Sprachen und , und möchten feststellen, ob es eine reguläre Sprache so dass und . Grundsätzlich besteht die Herausforderung darin, zu bestimmen, ob es einen DFA gibt, der erkennen kann, aus welcher der beiden Sprachen eine bestimmte Zeichenfolge stammt, sofern sie aus einer dieser Sprachen stammt.$A$$B$$R$$A \subseteq R$$R \cap B = \emptyset$

Ist das entscheidbar? Wenn ja, wie hoch ist die Komplexität? Kann der DFA explizit konstruiert werden?

Eryk Kopczyński [1] hat 2015 gezeigt, dass die Trennbarkeit (so heißt Ihr Problem) von sichtbaren Pushdown-Sprachen durch reguläre Sprachen nicht zu entscheiden ist. Die Klasse der sichtbaren Pushdown-Sprachen ist eine strenge Teilmenge der deterministischen CFL.

[1] Eryk Kopczyński, Invisible Pushdown Languages, LICS'16, verfügbar unter https://arxiv.org/abs/1511.00289