Рубрики

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 54

Пусть X — рекурсивный язык, а Y — рекурсивно перечислимый, но не рекурсивный язык. Пусть W и Z два таких языка, что Y 'сводится к W, а Z сводится к X' (сокращение означает стандартное сокращение много-один). Какое из следующих утверждений является ИСТИННЫМ
(A) W может быть рекурсивно перечислимым, а Z — рекурсивным.
(B) W может быть рекурсивным и Z рекурсивно перечислимым.
(C) W не рекурсивно перечислимо, а Z рекурсивно.
(D) W не является рекурсивно перечислимым и Z не является рекурсивным

Ответ: (с)
Объяснение: Поскольку X является рекурсивным, а рекурсивный язык закрыт при дополнении. Так что X ' также рекурсивен.
Поскольку Z X '   является рекурсивным (Правило: если Z сводится к X ', а X' рекурсивно, то Z рекурсивно. )
Вариант (B) и (D) исключен.
И Y является рекурсивным перечислимым, но не рекурсивным, поэтому Y 'не может быть рекурсивно перечислимым.
Так как Y 'сводится к W.
И мы знаем, что дополнение рекурсивного перечислимого не является рекурсивным перечислимым, и, следовательно, W не является рекурсивно перечислимым. Так что правильный вариант (С) .

Здесь Y 'является дополнением к Y
и X 'является дополнением к X.

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

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 54

0.00 (0%) 0 votes