10 Алгоритм Эрли продолжение Нормальная форма Грейбах

Алгоритм Эрли — алгоритм для проверки, распознаёт ли данная КС грамматика данное слово. Нормальная форма Грейбах — это форма контекстно-свободной грамматики, в которой правые части всех правил начинаются с терминального символа, за которым следует цепочка не-терминалов. Допускается правило с пустой цепочкой или терминалом, за которым следует только не терминал. Алгоритм приведения к нормальной форме Грейбаха требует грамматики без левой рекурсии. Сначала устраняют левую рекурсию, затем приводят грамматику к нормальной форме Грейбаха. Грамматика без левой рекурсии преобразуется в эквивалентную грамматику в нормальной форме Грейбаха. 00:05 Введение в алгоритм Эрли 00:36 Основные шаги алгоритма Эрли 01:01 Описание операций 03:03 Понимание алгоритма 04:44 Структура данных 06:46 Псевдокод алгоритма 09:41 Асимптотическая сложность 11:11 Подводные камни 11:59 Введение в множества и грамматики 12:31 Оценка длины дожитая 13:52 Операции и их выполнение 16:24 Операция комплект 20:46 Правило и его порождение 24:06 Дельта множества 29:12 Асимптотика алгоритма Эрли 31:56 Однозначные грамматики 34:00 Нормальная форма Грейбаха 38:32 Теорема о нормальной форме Грейбаха 40:08 Пример вывода не терминала 47:10 Введение в кейс 48:08 Логические размышления 50:25 Формальное доказательство 53:44 Доказательство леммы 01:02:28 Финальная часть доказательства 01:05:39 Заключение и выводы 01:07:34 Теорема о КС-языке и МП-автомате 01:08:26 Построение МП-автомата 01:09:44 Правила грамматики в нормальной форме Грейбаха 01:12:14 Преобразование правил 01:13:22 Замыкание эпсилон 01:15:04 Заключение