Определить, является ли язык контекстом бесплатным

Question

Допустим, у вас есть язык L, и вы хотите определить, свободен ли он от контекста. Контекстные бесплатные языки, пересекающиеся с регулярными языками, свободны от контекста. Достаточно ли этого, чтобы доказать, что L контекст свободен?

Значение,

L пересекает P = T, где Р является регулярным языком и Т является контекстно свободным. Означает ли это, что L свободен контекстом?

Answer 1

Нет, ваше сообщение является не true. Рассмотрим следующий встречный пример:

L = {0n1n2n | n > 0}, P = T = Ø. Очевидно, что у нас есть L ∩ P = L ∩ Ø = Ø = T, а Ø является как регулярным, так и контекстным.

Примечание: общеизвестно, что L не является контекстно-зависимым (see example on p.12 for a sketch proof by pumping lemma).