ДМ 1 курс - приведение грамматики к НФХ, алгоритм Кока-Янгера-Касами, автоматы с магазинной памятью

• Вопрос о том, выводится ли слово в контекстно-свободной грамматике, сложнее, чем для конечных автоматов.  

• Существует множество алгоритмов для решения этой задачи, зависящих от свойств грамматики.  

• Общий алгоритм работает за время, пропорциональное длине слова в кубе.  

• Общий алгоритм не подходит для больших входных данных, таких как исходный код или конфигурационные файлы.  

• Для таких задач используются специальные алгоритмы, работающие с грамматиками с дополнительными ограничениями.  

• Эти алгоритмы будут рассмотрены в другом предмете, но сегодня мы работаем с произвольными грамматиками.  

• Грамматику нужно преобразовать в нормальную форму Хомского НФХ для упрощения алгоритма.  

• НФХ требует, чтобы все правила имели один из двух видов: превращение терминала в два терминала или не терминала в терминал.  

• Разрешаются правила вида "эпсилон", но стартовый не терминал не может встречаться в правых частях правил.  

• Преобразование грамматики в НФХ включает два параллельных процесса: преобразование грамматики и проверка, выводится ли слово.  

• Первый шаг: добиться, чтобы в правых частях правил были только не терминалы.  

• Второй шаг: разрешить правила, которые в НФХ разрешены, и добавить личные не терминалы для терминалов.  

• Избавление от правил, содержащих терминалы и не терминалы в смешанном виде.  

• Введение личных не терминалов для терминалов и добавление правил для них.  

• Это позволяет сохранить множество слов, которые можно выразить, и упростить дерево разбора.  

• Избавление от эпсилон правил, цепных правил и длинных правил.  

• Оставление только правил, где терминалы в правых частях имеют нужный формат.  

• Это упрощает алгоритм и делает его более эффективным.  

• Рассматривается грамматика с правильной скобочной последовательностью.  

• Вводятся два нетерминала для открывающих и закрывающих скобок.  

• Грамматика преобразуется для удаления длинных правил.  

• Длинные правила заменяются на более короткие.  

• Вводятся вспомогательные нетерминалы для каждого правила.  

• Правила разбиваются на более мелкие части для упрощения разбора.  

• Сначала удаляются эпсон-правила, затем цепные правила.  

• Находятся эпсон-порождающие нетерминалы.  

• Алгоритм перебирает правые части правил для определения эпсон-порождающих нетерминалов.  

• Алгоритм проверяет, что все эпсон-порождающие нетерминалы помечены правильно.  

• Рассматривается минимальный контр-пример для доказательства корректности.  

• Алгоритм завершается, когда новых эпсон-порождающих нетерминалов не найдено.  

• Время работы алгоритма равно сумме длин правил, умноженной на количество нетерминалов.  

• Алгоритм работает за квадратичное время.  

• После удаления эпсон-правил, оставшиеся нетерминалы проверяются на порождаемость.  

• Если в правой части правила есть эпсон, порождающий не терминал, добавляем правила, где эпсон сразу убит.  

• Если оба эпсона порождающие, добавляем правила, где оба эпсона убиты.  

• Если все слово состоит из эпсона, добавляем новый стартовый символ э-штрих.  

• Добавляем новый стартовый символ э-штрих, если все слово состоит из эпсона.  

• Преобразуем грамматику, добавляя правила без эпсона.  

• Проверяем, что все слова можно разобрать без эпсон-правил.  

• Цепные правила создают циклы, что мешает динамике.  

• Строим граф цепных правил и делаем транзитивное замыкание.  

• Добавляем правила, чтобы избежать применения двух цепных правил подряд.  

• Преобразуем грамматику к нормальной форме Хомского.  

• Рассматриваем два типа правил: из терминала в терминал и из терминала в терминал.  

• Демонстрируем, как грамматика порождает правильные скобочные последовательности.  

• Преобразуем дерево разбора, избавляясь от терминалов в правых частях.  

• Устраняем длинные правые части, добавляя правила для иксов и игриков.  

• Убираем эпсон-правила и цепные правила, добавляя новые правила для упрощения разбора.  

• Обсуждение правил грамматики и их упрощения.  

• Преобразование грамматики для удобства обработки.  

• Преимущества бинарного дерева перед деревом с неизвестным количеством детей.  

• Введение в алгоритм Кока-Янгера-Касами.  

• Алгоритм как важный для своего времени, но менее значимый сейчас.  

• Описание входных данных и состояний динамического программирования.  

• Объяснение рекуррентной формулы для алгоритма.  

• Пример применения правил грамматики для порождения слов.  

• Упрощение правил для упрощения вычислений.  

• Порядок вычисления состояний динамического программирования.  

• Определение ответа и его вычисление.  

• Завершение алгоритма и его оценка по времени работы.  

• Размер грамматики определяется суммой длин правых частей правил.  

• В нормальной форме Хомского все правые части имеют длину два.  

• План лекции: обсуждение регулярных языков и их описания.  

• Регулярные выражения и автоматы описывают один и тот же язык.  

• Подход через порождение и распознавание строк.  

• Грамматики подходят под оба подхода.  

• Необходимость абстрактного вычислителя для проверки корректности скобочных последовательностей.  

• Введение нового абстрактного вычислителя, более мощного, чем конечный автомат.  

• Пример с палиндромами и использование стека для проверки корректности слов.  

• Автомат с магазинной памятью МП-автомат или стековая машина.  

• МП-автомат имеет состояния и переходы по символам или эпсилон.  

• Недетерминированные МП-автоматы распознают контекстно-свободные языки.  

• Переход автомата: чтение текущего символа и переход к следующему.  

• Изменение стека: снятие символа со стека и замена его на новый символ.  

• Пример с правильными скобочными последовательностями и использованием стека как счетчика.  

• Рассматривается автомат с магазинной памятью для проверки правильности скобочных последовательностей.  

• Вводится понятие баланса, который увеличивается при добавлении символов в стек.  

• Обсуждается, как обрабатывать открывающие и закрывающие скобки.  

• Вводится дополнительное состояние для допуска, если стек пуст.  

• Автомат становится не детерминированным, что позволяет ему допускать правильные последовательности.  

• Обсуждается, как избежать ошибок при допуске.  

• Создается автомат для проверки палиндромов, который имеет два состояния.  

• Вводится синтаксический сахар для упрощения переходов.  

• Обсуждается, как автомат принимает решения о переходе в зависимости от символов в стеке.  

• Вводится понятие входного и стекового алфавитов.  

• Описывается множество состояний и стартовое состояние.  

• Обсуждается функция переходов, которая принимает текущее состояние, символ со входа и символ из стека.  

• Автомат может иметь несколько переходов, но только конечное их количество.  

• Обсуждается, почему важно ограничивать переходы для конечных автоматов.  

• Вводится понятие допуска по пустому стеку, что эквивалентно допуску по допускающему состоянию.  

• Обсуждается, что автомат может заканчиваться одновременно с опустошением стека и окончанием слова.  

• Это свойство будет обсуждаться на следующей лекции и станет фундаментальным для построения КС-грамматик.