Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 48

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

Ответ: (D)
Объяснение:
Язык рекурсивно перечислим, если существует машина Тьюринга, которая принимает каждую строку языка и не принимает строки, которых нет в языке.
Строки, отсутствующие в языке, могут быть отклонены или могут привести к тому, что машина Тьюринга войдет в бесконечный цикл.

Рекурсивный язык не может зайти в бесконечный цикл, он должен явно отклонять строку, но рекурсивно перечислимый язык может зайти в бесконечный цикл.

Итак, каждый рекурсивный язык также рекурсивно перечислим.
Таким образом, утверждение «Каждое подмножество рекурсивно перечислимого множества является рекурсивным» неверно.

Таким образом, вариант (D) является ответом.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

Тест на этот вопрос

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

ВОРОТА | GATE CS 2008 | Вопрос 48

0.00 (0%) 0 votes