Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 33

Пусть 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), неразрешима.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2006 | Вопрос 33

0.00 (0%) 0 votes