Учитывая, что PDA M такой, что L (M) находится в DCFL, строят DPDA N такой, что L (N) = L (M)

Можно ли построить алгоритм, который принимает в качестве входных данных автомат сокращения вместе с обещанием, что язык, принятый этим автоматом является детерминированным контекстно-свободным языком и выводит детерминированный автомат нажатия который принимает именно принятый язык на ?$M$$L(M)$$N$$M$

Эквивалентная проблема была бы построить алгоритм , который принимает в качестве входного магазинного автомата (с обещанием , что является детерминированным, как указаны выше) и детерминированными магазинными автоматами . Вывод будет да, если и нет, если .$M$$L(M)$$N$$L(M) = L(N)$$L(M)\neq L(N)$

Я полагаю, что алгоритм, решающий первое, дал бы алгоритм, решающий второе по разрешимости эквивалентности детерминированных автоматов. Я думаю, что решение для второго означало бы решение для первого, поскольку мы перечисляем все детерминированные автоматы нажатия и запускаем алгоритм для них один за другим, как только мы получаем экземпляр yes, мы выводим этот автомат.

Интересно, кто-нибудь знает что-нибудь об этом? Может быть, это известная проблема и / или есть известное решение? Кроме того, я считаю, что это можно решить, если вы введете ограничение, которое говорит о том, что язык, сгенерированный КПК, является проблемой слова группы.

Возьмем детерминированный ТМ $M$ и слово $w$ . Рассмотрим историю его вычислений для слова $w$ . Пусть $L$ будет недействительными историями (те, которые не начинаются с $w$ , не заканчиваются принятием или являются недействительными). Либо $L = A^{\ast}$ ( $M$ не принимает $w$ ), либо $L = A^{\ast} - \{h\}$ для некоторой строки $h$ ( $M$ принимает $w$ с историей вычислений $h$ ). Прежде всего, $L$является эффективным CFL, в том смысле, что вы можете построить грамматику / КПК, распознавая его. Кроме того, $L$ является (неэффективным) DCFL, но вы не можете показать DPDA для него эффективно. Более того, $L$ (неэффективно) регулярно.

Небольшое уточнение:

Вы спросили, разрешима ли следующая проблема:

данный PDA $M$ обещал, что $L(M)$ является DCFL, а DPDA $N$ определяет, является ли $L(M) = L(N)$ .

Ответ - нет, и на самом деле имеет место следующий более сильный факт: следующая проблема неразрешима:

учитывая, что КПК $M$ обещал, что $L(M)$ является регулярным, определите, если $L(M)=A^{\ast}$ .