Формальные языки и трансляции 6. Автомат с магазинной памятью

0:10 - Незамкнутость КС-языков относительно пересечения и дополнения 4:37 - Упражнение (дополнение не КС-языка) 6:25 - Алгоритм, распознающий ПСП 8:27 - Основные определения 21:54 - Свойства МП-автоматов 26:35 - Лемма об эквивалентности МП-автоматов МП-автоматам определенного вида 30:31 - Теорема о распознавании КС-языков МП-автоматами 31:10 - Первая часть доказательства: автомат порождает грамматику 37:32 - Лемма 1:04:43 - Вторая часть доказательства: грамматика порождает автомат 1:09:07 - Лемма Лекция от 11 октября 2019 Лектор: Сорокин Алексей Андреевич Оператор - Рухадзе Альбина Монтаж - Юманов Михаил