Является ли контекстно-свободный язык детерминированным контекстно-свободным языком

Question

Пусть L (G) - язык, генерируемый контекстно-свободной грамматикой G. Является ли разрешимой следующая проблема решения?Является ли L (G) детерминированным контекстно-свободным языком?

Я понял, почему указанная выше проблема неразрешима из этой ссылки , но у меня были сомнения.Мы знаем, что КЛЛ и КПК эквивалентны ( ссылка ), т. Е. Для каждого КЛЛ, G, существует КПК М, такой что L (G) = L (M) и наоборот.Контекстно-свободный язык является детерминированным, если он может быть принят DPDA.Детерминированный КПК - это тот, в котором возможен не более одного возможного перехода из любого состояния на основе текущего ввода.Поскольку мы можем создать PDA для каждого CFL и различать, является ли PDA детерминированным или нет, можем ли мы сказать, что проблема того, является ли L (G) детерминированным контекстно-свободным языком, разрешима?Или я что-то упустил?

Answer 1

Вы что-то упустили.Вы говорите:

Контекстно-свободный язык является детерминированным, если он может быть принят DPDA.

и

мы можем создатьКПК для каждого КЛЛ

и

[мы можем] различать, является ли КПК детерминированным или нет

Проблема в том, что КПК выget для CFL может быть недетерминированным, даже если язык является детерминированным.Хотя верно, что каждый детерминированный CFL имеет DPDA, который его принимает, неверно, что каждый детерминированный CFL принимается ТОЛЬКО DPDA.Действительно, каждый детерминированный КЛЛ принимается многими недетерминированными КПК ... Нетрудно понять, что любой DPDA может быть преобразован в эквивалентный недетерминированный КПК путем добавления новых состояний и ветвей, которые не приводят к принятию чего-либо.