Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 32

Пусть L — контекстно-свободный язык, а M — обычный язык. Тогда язык L ∩ M
(А) всегда регулярно
(Б) никогда не регулярно
(C) всегда детерминированный контекстно-свободный язык
(D) всегда язык без контекста

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

L является контекстно-свободным языком, а M — обычным языком, а значит, и контекстно-свободным. Следовательно, L ∩ M наверняка не зависит от контекста в соответствии с законами закрытия контекстно-свободных языков. Нам нужно проверить, будет ли это всегда или не всегда. Мы можем доказать, что приведением примеров st L ∩ M может быть как регулярным, так и нерегулярным.
• L = {a n b n | n ≥ 0} и M = a * b *, в этом случае L ∩ M будет само L, следовательно, не зависит от контекста, но не является регулярным. L ∩ M также не будет детерминированным CFL каждый раз, как в этом примере.
L = {a n b n | n ≥ 0} и M = a, в этом случае L ∩ M будет само M, следовательно, регулярным.

Учитывая приведенное выше утверждение, правильным ответом будет (D) всегда язык без контекста.

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

ВОРОТА | GATE IT 2006 | Вопрос 32

0.00 (0%) 0 votes