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

Таймкоды:
0:00 Начало
2:41 Как вернуть пустое слово в грамматике Хомского(шаг 6)
7:04 Удаление цепных правил(шаг 7)
15:23 Свойства грамматики Хомского
17:33 Задача парсинга
18:24 Алгоритм Кока-Янгера-Касами
24:17 Асимптотика
26:41 Лемма о разрастании для КС-языков
37:24 Пример не контекстно свободного языка
42:15 Следствия из леммы о разрастании
47:23 Утверждение о пересечении КС-языка и регулярного
49:00 Автоматы с магазинной памятью
55:10 Конфигурация МП-автомата
56:30 Выводимость
59:51 Упрощения автоматов
1:02:34 Следствие
1:03:39 КС-граматики в МП-автоматы

Лектор: Ахтямов Павел Ибрагимович
Дата лекции: 15.10.2024

Оператор: Савельев Е.
Монтажер: Андреев Я.

Плейлист:    • Формальные языки и трансляции (2 курс...