Zwykły język, który rozróżnia dwa deterministyczne CFG

Załóżmy, że masz dwa deterministyczne automaty wypychające, które rozpoznają języki i B , i chcesz ustalić, czy istnieje regularny język R, taki jak A ⊆ R i R ∩ B = ∅ . Zasadniczo wyzwanie polega na ustaleniu, czy istnieje DFA, który może rozpoznać, który z dwóch języków pochodzi z danego łańcucha, biorąc pod uwagę, że pochodzi on z jednego z tych języków.$A$$B$$R$$A \subseteq R$$R \cap B = \emptyset$

Czy jest to możliwe? Jeśli tak, jaka jest złożoność? Czy DFA można zbudować wyraźnie?

Eryk Kopczyński [1] pokazał w 2015 r., Że rozróżnienie (to nazwa twojego problemu) widocznych języków popychanych przez zwykłe języki jest nierozstrzygalne. Klasa widocznych języków wypychania jest ścisłym podzbiorem deterministycznego CFL.

[1]: Eryk Kopczyński, Invisible Pushdown Languages, LICS'16, dostępny na https://arxiv.org/abs/1511.00289