Решите, могут ли контекстно-свободные языки быть приняты детерминированным автоматом

При наличии не зависящей от контекста грамматики G существует недетерминированный автомат Pushdown N, который принимает именно тот язык, который принимает G. (и наоборот)

Там может также существовать детерминированный магазинный автомат D , который принимает именно язык G принимает слишком. Это зависит от грамматики.

По какому алгоритму на произведениях G мы можем определить, существует ли D?

Не существует алгоритма, который бы давал контекстно-свободную грамматику, определяющий, распознает ли DPDA тот же язык и вычисляет его, если он существует.

Поскольку, если бы существовал такой алгоритм, мы могли бы решить неразрешимую проблему универсальности контекстно-свободной грамматики, т. Е. Распознает ли данная контекстно-свободная грамматика на весь язык Σ ^ * .Σ Σ$G$$Σ$$Σ^*$

Предположим, есть такой алгоритм $A_{DPDA}$ . Пусть $G$ некоторая не зависящая от контекста грамматика. Пусть $L$ будет $\mathcal L(G)$ . Тогда алгоритм $A_{DPDA}$ будет решить , если есть DPDA распознавания л .$A$$L$

• Если такого DPDA нет, то $L$ не распознается DPDA, в частности он не является регулярным, поэтому он не может быть $Σ^*$ .

• Если DPDA существует, то мы можем решить , равно ли потому что универсальность решаема для DPDA. Зачем? Потому что:L Σ$A$$L$$Σ^*$

  • Языки DPDA закрыты при дополнении (поскольку DPDA являются детерминированными)
  • пустота разрешима для DPDA (потому что это для КПК )

Используя мы построили алгоритм, решающий, будет ли для любой не зависящей от контекста грамматики , что оказалось невозможным. Следовательно, не существует. L ( G ) = Σ ∗ G A D P D $A_{DPDA}$$L(G)=Σ^*$$G$$A_{DPDA}$