Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 15

Что из следующего является ЛОЖНЫМ?

(A) Существует уникальный минимальный DFA для каждого обычного языка
(B) Каждый NFA может быть преобразован в эквивалентный PDA.
(C) Дополнение к любому контекстно-свободному языку является рекурсивным.
(D) Каждый недетерминированный КПК может быть преобразован в эквивалентный детерминированный КПК.

Ответ: (D)
Пояснение: Мощность детерминированного КПК не равна мощности недетерминированного КПК. Детерминированный PDA не может обрабатывать языки или грамматики с неоднозначностью, но NDPDA может обрабатывать языки с неоднозначностью и любой контекстно-свободной грамматикой. Таким образом, каждый недетерминированный КПК не может быть преобразован в эквивалентный детерминированный КПК.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2009 | Вопрос 15

0.00 (0%) 0 votes