Формальные языки 7. Лемма о разрастании для КС-языков. МП-автоматы

00:00:00 - «Ситуация очень плачевная...» 00:01:20 - Что было раньше? 00:03:38 - Лемма о разрастании для КС-языков 00:12:35 - Дерево разбора и принцип Дирихле 00:21:51 - Пример языка, не являющегося контестно-свободным 00:27:50 - Почему КС-языки не замкнуты относительно пересечения? 00:30:09 - Почему КС-языки не замкнуты относительно дополнения? 00:34:11 - Автоматы с магазинной памятью (МП-автоматы) 00:36:46 - Как выглядят переходы? 00:38:26 - Конфигурация и отношение выводимости 00:42:25 - Пример МП-автомата 00:47:10 - Упрощения МП-автоматов 00:53:10 - Как связаны между собой МП-автоматы и КС-языки? Дата лекции: 19.10.2021 Лектор: Ахтямов Павел Монтаж: Алексей Горбулев