Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 55

GATE

Рассмотрим языки:

L1 = {anbncm | n, m > 0} 
L2 = {anbmcm | n, m > 0}

Какое из следующих утверждений ЛОЖНО?
(A) L1 ∩ L2 — это контекстно-свободный язык
(B) L1 U L2 — это контекстно-свободный язык
(C) L1 и L2 являются контекстно-свободным языком
(D) L1 ∩ L2 является контекстно-зависимым языком

Ответ: (А)
Объяснение: Мы можем распознать строки данного языка, используя один стек. Эти данные языки не зависят от контекста, а также чувствительны к контексту.
Поскольку КЛЛ закрыты в соответствии с собственностью Союза, объединение данных языков также будет не зависящим от контекста.
Но КЛЛ не являются закрытыми в соответствии с свойством Пересечение, поэтому пересечение двух КЛЛ не может быть КЛЛ.
Учитывая, что L1 и L2 являются двумя контекстно-свободными языками, их пересечение L1 ∩ L2 не является контекстно-свободным, поскольку мы не можем идентифицировать строки результирующего языка с помощью одного стека:

L1 = {a n b n c m | n> 0 и m> 0} и L2 = {a m b n c n | n> 0 и m> 0}

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

ВОРОТА | GATE-CS-2005 | Вопрос 55

0.00 (0%) 0 votes