Рубрики

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

Для любых двух языков L1 и L2, таких, что L1 не зависит от контекста, а L2 рекурсивно перечислим, но не рекурсивен, что из следующего является / обязательно истинным?

1. L1' (complement of L1) is recursive 
2. L2' (complement of L2) is recursive
3. L1' is context-free 
4. L1' ∪ L2 is recursively enumerable 

(A) 1 только
(B) только 3
(C) только 3 и 4
(D) 1 и 4 только

Ответ: (D)
Пояснение: 1. L1 ′ (дополнение к L1) рекурсивно верно
L1 не зависит от контекста. Каждый контекстно-свободный язык также является рекурсивным, а рекурсивные языки закрыты в дополнении.

4. L1 ′ ∪ L2 рекурсивно перечислимо верно
Поскольку L1 ′ является рекурсивным, он также рекурсивно перечислим и рекурсивно перечислимые языки закрыты при объединении .
Рекурсивно перечислимые языки известны как языки типа 0 в иерархии формальных языков Хомского. Все обычные, контекстно-свободные, контекстно-зависимые и рекурсивные языки рекурсивно перечислимы. (Источник: Вики )

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

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

0.00 (0%) 0 votes