Вопросы по курсу «Теория автоматов и формальные языки»
1. Инженерное определение конечного автомата. Автоматы Мили и Мура. Состояния, переходы, входной и выходной управляющий символы и алфавиты. Представление автомата табличной формой, графом. Синтез автомата.
2. Порождающие (формальные) грамматики. Определение. Классификация по Хомскому. Отношения вывода. Лево - и правосторонний вывод. Язык, порождаемый грамматикой.
3. Дерево синтаксического разбора (сентенциальная форма). Представление вывода цепочки деревом разбора. Проблема неоднозначности вывода. Достаточные условия неоднозначности грамматики. Нисходящий и восходящий, лево - и правосторонний методы разбора. Реализация нисходящего левостороннего разбора методом рекурсивного спуска.
4. Конечные автоматы и задача распознавателя, его определение, классификация распознавателей и их структурные схемы. Определение, способы задания КА, функционирование, примеры. Связь между регулярными грамматиками и конечными автоматами. Язык, допустимый КА. Детерминированные и недетерминированные КА, теорема о детерминизации (построение эквивалентного КА). Реализация универсального таблично-управляемого детерминированного КА.
5. Регулярные грамматики, множества и выражения. Определения, примеры. Автоматные и регулярные языки, построение эквивалентного автоматного языка по регулярному. Построение полной переходной функции. Проблема неоднозначности переходной функции, детерминированные (ДКА) и недетерминированные (НКА) конечные автоматы. Алгоритм преобразования автомата в ДКА, удаление недостижимых состояний. Теорема об определении и характеризации регулярных языков. Особенности дерева вывода по РГ.
6. Лемма о разрастании для регулярных языков. Примеры нерегулярных языков. Теорема Майхилла-Нерода о единственном минимальном КА (без док-ва).
7. Контекстно-свободные языки и грамматики. Определение, примеры. Нормальная форма Хомского. Теорема о порождении контекстно свободного языка грамматикой в форме Хомского. Нормальная форма Грейбах. Теорема об «удаляемости» из КС-грамматик рекурсивных слева продукций. Достижимые свойства и эквивалентные преобразования КС-грамматик.
8. Магазинные (МП) автоматы и КС-языки. Определение, примеры, функционирование. Классы детерминированных и недетерминированных МА.
9. Недетерминированный нисходящий и восходящий разбор по КС-грамматике. Построение моделирующих магазинных автоматов. Детерминированный разбор с возвратами.
