Чтобы доказать, что контекстно-свободные языки не закрыты на пересечении, приведем контрпример.
Рассмотрим L = {a ^ i b ^ j c ^ k | i = j} и R = {a ^ i b ^ j c ^ k | я = к}. Пересечение этих двух множеств есть S = {a ^ i b ^ j c ^ k | i = j = k}, то есть строки вида a ^ n b ^ n c ^ n. Используя лемму прокачки для контекстно-свободных языков, можно показать, что этот язык не является контекстно-свободным. Контекстно-свободные грамматики для двух других просты:
L is given by
S := AC
A := aAb | lambda
C := cC | lambda
R is given by
S := aSc | B | lambda
B := bB | lambda
Чтобы ответить на ваш вопрос более конкретно, причина, по которой обе теоремы могут быть верными, состоит в том, что обычные языки являются надлежащим подмножеством языков без контекста; для того чтобы языки без контекста были закрыты при заданном пересечении, пересечение любых произвольных языков без контекста также должно быть свободным от контекста (это не так; см. выше). Однако в то же время верно, что случай, когда пересечение любого обычного языка и любого языка, свободного от контекста, также не является контекстным (нет причины, по которой машина декартовых произведений не может быть создана с использованием FA и КПК, в конце концов, только одна машина нуждается в стеке, в отличие от случая, когда при работе с машиной с декартовым продуктом используется два КПК, поскольку в некоторых случаях требуется два стека, а два стековых КПК эквивалентны машинам Тьюринга).