ВОРОТА | ВОРОТА КС 2021 | Набор 2 | Вопрос 22

Пусть L ₁ — регулярный язык, а L ₂ — контекстно-свободный язык. Какой из следующих языков является/являются контекстно-свободными?
(А) L ₁ ∩ L ₂ '
(Б) (L ₁ '∪L ₂ ')'
(С) _L1 ∪( _{L2 ∪L2} ')
(D) ( _{L1 ∩L2} )∪( _{L1 ∩L2} )

Ответ: (Б) (В) (Г)
Объяснение:

• (A) Регулярное объединение CSL = CSL. Неверный вариант
• (B) (L1'U L2')' можно записать как (L1 ∩ L2)». Таким образом, после упрощения это будет L1 ∩ L2, следовательно, это CFL. Правильный вариант.
• (C) L2 U L2′ означает, используя логику дополнений, его универсальное множество, представленное Σ*. Таким образом, любое объединение с Σ * является самим Σ *, а Σ * является регулярным, следовательно, по умолчанию также является его CFL. Правильный вариант
• (D) (L1∩L2)∪(L1∩L2), Здесь мы ясно наблюдаем CFL U CFL = CFL. Правильный вариант.

Викторина этого вопроса