15. Замкнутость КС-языков относительно КП

Класс контекстно-свободных (КС) языков не замкнут относительно пересечения и дополнения. Например, пересечение двух КС-языков может не быть КС-языком. Однако пересечение КС-языка с регулярным языком всегда даёт КС-язык. 00:00 Введение и теорема Неванкина 01:29 Константа Липшица 03:56 Построение прообраза слова 05:55 Применение тождественного преобразования 06:48 Применение не удлиняющего гомоморфизма 10:09 Обратный гомоморфизм 12:10 Построение контекстно-свободной грамматики 18:02 Лемма разрастания 21:59 Преобразование слов 25:22 Пример с двоичной системой 26:28 Базовая морфология 27:25 Контекстно-свободные и регулярные языки 33:02 Линейная оболочка 36:51 Сумма множеств 38:21 Линейные множества 40:40 Полулинейные множества 43:05 Регулярный прообраз 47:05 Линейная оболочка 52:26 Теорема Парика 55:04 Лемма о разрастании 01:03:07 Введение в подмножество терминалов 01:04:34 Цель и доказательство 01:07:19 Доказательство конечности множеств 01:08:00 Доказательство в одну сторону 01:16:27 Доказательство в обратную сторону 01:24:10 Заключение