Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 56

Пусть L1 — рекурсивный язык, и пусть L2 — рекурсивно перечислимый, но не рекурсивный язык. Что из следующего является ИСТИННЫМ?

L1' --> Complement of L1
L2' --> Complement of L2 

(A) L1 ′ рекурсивно, а L2 ′ рекурсивно перечислимо
(B) L1 ′ рекурсивно, а L2 ′ не рекурсивно перечислимо
(C) L1 ′ и L2 ′ рекурсивно перечислимы
(D) L1 ′ рекурсивно перечислимо, а L2 ′ рекурсивно

Ответ: (Б)
Объяснение: Рекурсивно перечислимые языки известны как языки типа 0 в иерархии формальных языков Хомского . Все обычные , не зависящие от контекста , контекстно-зависимые и рекурсивные языки рекурсивно перечислимы (Источник: http://en.wikipedia.org/wiki/Recursively_enumerable_language )

Рекурсивные языки закрыты при дополнении, но рекурсивно перечислимые не закрыты при дополнении . Если языки L рекурсивно перечислимы, то дополнение к рекурсивно перечислимо тогда и только тогда, когда L также рекурсивно. Поскольку L2 рекурсивно перечислим, но не рекурсивен, L2 ′ не рекурсивно перечислим.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2005 | Вопрос 56

0.00 (0%) 0 votes