Содержание 1 Формальные языки и грамматики .......................................................................... 1.1 Операции над цепочками символов .................................................................... 1.2 Способы задания языков...................................................................................... 1.2.1 Определение языков посредством множеств................................................... 1.2.2 Формы Бэкуса-Наура ........................................................................................ 1.2.3 Диаграммы Вирта.............................................................................................. 1.2.4 Формальные грамматики .................................................................................. 1.2.4.1 Определение формальной грамматики ......................................................... 1.2.4.2 Классификация языков и грамматик ............................................................. 1.2.4.3 Эквивалентность грамматик .......................................................................... 1.2.5 Механизмы распознавания языков................................................................... 1.2.5.1 Определение распознавателя......................................................................... 1.2.5.2 Схема работы распознавателя ....................................................................... 1.2.5.3 Классификация распознавателей................................................................... 2 Регулярные языки ................................................................................................... 2.1 Регулярные выражения ........................................................................................ 2.2 Лемма о разрастании для регулярных языков .................................................... 2.3 Конечные автоматы.............................................................................................. 2.3.1 Определение конечного автомата .................................................................... 2.3.2 Распознавание строк конечным автоматом ..................................................... 2.3.2.1 Построение конечного автомата по регулярной грамматике ...................... 2.3.3 Преобразование конечных автоматов .............................................................. 2.3.3.1 Преобразование конечного автомата к детерминированному виду............ 2.3.3.2 Минимизация конечного автомата................................................................ 2.3.3.2.1 Устранение недостижимых состояний автомата ....................................... 2.3.3.2.2 Объединение эквивалентных состояний автомата .................................... 3 Контекстно-свободные языки................................................................................. 3.1 Задача разбора ...................................................................................................... 3.1.1 Вывод цепочек................................................................................................... 3.1.2 Дерево разбора .................................................................................................. 3.1.2.1 Нисходящее дерево разбора........................................................................... 3.1.2.2 Восходящее дерево разбора ........................................................................... 3.1.3 Однозначность грамматик ................................................................................ 3.2 Преобразование КС-грамматик .......................................................................... 3.2.1 Проверка существования языка........................................................................ 3.2.2 Устранение бесполезных символов грамматики............................................. 3.2.3 Устранение -правил......................................................................................... 3.2.4 Устранение цепных правил .............................................................................. 3.2.5 Левая факторизация правил.............................................................................. 3.2.6 Устранение прямой левой рекурсии ................................................................ 3.3 Автомат с магазинной памятью .................

---

Смотрите также файлы

• Законодательства в филиале акб Росэнергобанка.docx

• Тактична медицина.docx

• Организационная структура гражданской обороны. Сигналы оповещения и действия личного состава при получении сигналов оповещения.docx

• Тркістан облысы Тлкібас ауданы.docx

• Атааналар жиналысыны Хаттамасы .docx