Рубрики

ВОРОТА | GATE CS 2011 | Вопрос 24

1) Пусть P — обычный язык, а Q — язык без контекста, такой что Q P. (Например, пусть P будет языком, представленным регулярным выражением p * q *, а Q будет {p n q n | n N}). Тогда что из следующего ВСЕГДА регулярно?
(А) П Q
(B) P — Q
(С) * — П
(D) * — Q

(А) А
(Б) Б
(С) С
(D) D

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

1. P ∩ Q будет Q из-за того факта, что Q ⊆ P, следовательно, не зависит от контекста, но не является регулярным.
2. P — Q = P ∩ Q может даже не быть контекстно-свободным языком из-за свойств замыкания контекстно-свободных языков.
3. Σ ∗ — P является эквивалентным дополнением к P, следовательно, является регулярным. Обратитесь к законам закрытия обычных языков.
4. Σ ∗ — Q эквивалентно дополняет Q, следовательно, он может даже не быть контекстно-свободным языком.

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

ВОРОТА | GATE CS 2011 | Вопрос 24

0.00 (0%) 0 votes