ВОРОТА | 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 ′ не рекурсивно перечислим.
Тест на этот вопрос

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

• ВОРОТА | 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