Что из следующего является ЛОЖНЫМ?
(A) Существует уникальный минимальный DFA для каждого обычного языка
(B) Каждый NFA может быть преобразован в эквивалентный PDA.
(C) Дополнение к любому контекстно-свободному языку является рекурсивным.
(D) Каждый недетерминированный КПК может быть преобразован в эквивалентный детерминированный КПК.
Ответ: (D)
Пояснение: Мощность детерминированного КПК не равна мощности недетерминированного КПК. Детерминированный PDA не может обрабатывать языки или грамматики с неоднозначностью, но NDPDA может обрабатывать языки с неоднозначностью и любой контекстно-свободной грамматикой. Таким образом, каждый недетерминированный КПК не может быть преобразован в эквивалентный детерминированный КПК.
Тест на этот вопрос
Рекомендуемые посты:
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
- ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65
0.00 (0%) 0 votes