Пусть L1 — обычный язык, L2 — детерминированный контекстно-свободный язык, а L3 — рекурсивно перечислимый, но не рекурсивный язык. Какое из следующих утверждений является ложным?
(A) L1 ∩ L2 является детерминированным КЛЛ
(B) L3 ∩ L1 является рекурсивным
(C) L1 ∪ L2 не зависит от контекста
(D) L1 ∩ L2 ∩ L3 рекурсивно перечислимо
Ответ: (Б)
Объяснение:
(A) Это утверждение верно, потому что детерминированные контекстно-свободные языки закрыты на пересечении с обычными языками.
(B) Это утверждение неверно, потому что L1 рекурсивен, и каждый рекурсивный язык разрешим. L3 рекурсивно перечислим, но не рекурсивен. Итак, L3 неразрешима. Пересечение рекурсивного языка и рекурсивного перечислимого языка является рекурсивно перечислимым.
(C) Это утверждение верно, потому что L1 регулярно. Каждый обычный язык также является языком без контекста. L2 — это детерминированный контекстно-свободный язык, и каждый DCFL также является контекстно-свободным языком. Каждый контекстно-свободный язык закрыт в рамках Союза.
(D) Это утверждение верно, поскольку L1 является регулярным, следовательно, оно также рекурсивно перечислимо. L2 является детерминированным контекстно-свободным языком, поэтому он также рекурсивно перечислим. Рекурсивно перечислимые языки закрыты на пересечении.
Таким образом, проблема, упомянутая в варианте (A), неразрешима.
Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.
Рекомендуемые посты:
- ВОРОТА | 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
0.00 (0%) 0 votes