Обычный язык, который различает два детерминированных CFG

Предположим, вам даны два детерминированных автомата нажатия, которые распознают языки и B , и хотите определить, существует ли регулярный язык R такой, что A ⊆ R и R ∩ B = ∅ . По сути, задача состоит в том, чтобы определить, существует ли DFA, способный распознавать, из какого из двух языков поступает данная строка, учитывая, что она происходит от одного из этих языков.$A$$B$$R$$A \subseteq R$$R \cap B = \emptyset$

Это решаемо? Если да, то в чем сложность? Можно ли построить DFA явно?

Эрик Копчинский [1] показал в 2015 году, что разделимость (это название вашей проблемы) визуально распространяемых языков на обычные языки неразрешима. Класс визуально распространяемых языков является строгим подмножеством детерминированного КЛЛ.

[1]: Эрик Копчинский, «Невидимые языки пуш-апа», LICS'16, доступен по адресу https://arxiv.org/abs/1511.00289.