Рубрики

ВОРОТА | GATE CS 2013 | Вопрос 32

Рассмотрим следующие языки.

Какое из следующих утверждений ЛОЖНО?
(A) L2 не зависит от контекста.
(B) L1 пересечение L2 не зависит от контекста.
(C) Дополнение L2 является рекурсивным.
(D) Дополнение к L1 не зависит от контекста, но не является регулярным.

Ответ: (Д)
Объяснение: (D) неверно.

L1 регулярный, поэтому его дополнение также будет регулярным.

L1 — обычный язык вида 0 ^ * 1 ^ * 0 ^ *. С другой стороны, L2 — это CFL, так как он может быть получен из следующего CFG
L2 = {0 ^ p 1 ^ q 0 ^ r | p, q, r> 0 и p notEqualTo r}
S -> AC | CA
C -> 0C0 | B
A -> 0A | 0
B -> 1B | эпсилон
Если придумать CFG для L2 сложно, можно интуитивно увидеть это, сократив его до более простой проблемы. L2 очень похож на известный КЛЛ L3 = {a ^ mb ^ l | не равны}

(A) L2 не зависит от контекста, что верно [ПРАВИЛЬНО]
(B) L1 пересечение L2 не зависит от контекста, что опять-таки верно, потому что L1 является обычным языком, а L2 является CFL. RL union CFL — это всегда CFL. Следовательно [ПРАВИЛЬНО]
(C) Дополнение L2 является рекурсивным, что верно в силу того факта, что дополнением к CFL наверняка является CSL (контекстно-зависимый язык), который в свою очередь (CSL) является подмножеством рекурсивных языков. Следовательно [ПРАВИЛЬНО]
(D) Дополнение к L1 не зависит от контекста, но не является регулярным, что неверно из-за законов закрытия обычных языков. Дополнением к RL всегда является RL. Следовательно [НЕПРАВИЛЬНО]

Это решение предоставлено Vineet Purswani .
Тест на этот вопрос

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

ВОРОТА | GATE CS 2013 | Вопрос 32

0.00 (0%) 0 votes