Теория автоматов, языков и вычислений

Description

Теория автоматов, языков и вычислений : учебное пособие [Электронный ресурс] / сост. Д.В. Семенова, В.В. Быкова......Page 1 Оглавление......Page 3 Введение......Page 6 1.1.1 Алфавит. Цепочка......Page 7 1.1.2 Операции над цепочками......Page 9 1.2. Определение языка......Page 12 1.3.1. Теоретико-множественные операции над языками......Page 13 1.3.2. Специальные операции над языками и их свойства......Page 14 1.3.3. Способы определения формальных языков......Page 21 Контрольные вопросы и упражнения......Page 22 Задачи для самостоятельного решения......Page 23 Глава 2. Регулярные языки и выражения......Page 26 2.1. Регулярные множества и выражения......Page 27 2.2. Регулярные языки......Page 30 2.2.1. Свойства регулярных языков......Page 32 2.2.2. Языки, определяемые уравнениями......Page 33 2.2.3. Стандартные системы уравнений с регулярными коэффициентами......Page 37 Задачи для самостоятельного решения......Page 41 3.1. Порождающая грамматика Хомского......Page 44 3.1.1. Отношение выводимости......Page 46 3.2. Языки, порождаемые грамматиками......Page 48 3.2.2. Классификация грамматик и языков по Хомскому......Page 49 3.2.3. Соотношение между типами грамматик и языков......Page 51 3.2.4. Примеры грамматик и языков......Page 53 3.3. Разбор цепочек в КС-грамматике......Page 55 3.3.1. Размеченный вывод......Page 56 3.3.2. Дерево вывода......Page 57 3.3.3. Неоднозначность грамматик......Page 62 3.4. Эквивалентные преобразования КС-грамматик......Page 67 3.4.1. Удаление бесполезных символов......Page 68 3.4.2. е-свободные символы КС-грамматики......Page 73 3.4.3. Исключение ценных правил......Page 75 3.4.4. Удаление произвольного правила вывода......Page 80 3.4.5. Нормальная форма Хомского......Page 81 3.4.6. Устранение левой рекурсии......Page 84 3.4.7. Нормальная форма Грейбах......Page 88 Контрольные вопросы и упражнения......Page 94 Задачи для самостоятельного решения......Page 96 Глава 4. Элементы теории автоматов......Page 100 4.1. Понятие автомата......Page 101 4.2. Распознаватели......Page 104 4.2.1. Классификация распознавателей по виду их компонентов......Page 106 4.2.2. Классификация распознавателей по типам распознаваемых языков......Page 108 4.3.1. Недетерминированный конечный автомат......Page 110 4.3.2. Детерминированный конечный автомат......Page 117 4.3.3. Конечные автоматы и грамматики типа 3......Page 121 4.3.4. Основные свойства автоматных языков......Page 128 4.4.1. Определение автомата с магазинной памятью......Page 130 4.4.2. Эквивалентность МП-автоматов и КС-грамматик......Page 138 4.4.3. Детерминированные МП-автоматы......Page 146 4.5.1. Машины Тьюринга......Page 148 4.5.2. Машины Тьюринга и грамматики типа 0......Page 151 4.5.3. Линейно ограниченные автоматы и контекстно-зависимые языки......Page 152 Контрольные вопросы и упражнения......Page 155 Задачи для самостоятельного решения......Page 157 Глава 5. Элементы теории сложности вычислений......Page 161 5.1. Алгоритмы и задачи......Page 162 5.2. Концептуальные основы анализа алгоритмов......Page 165 5.3. Асимптотические формализмы, используемые в анализе алгоритмов......Page 170 5.4. Классификация алгоритмов по сложности......Page 175 5.5. Основные приемы анализа итерационных алгоритмов......Page 178 5.6. Основные приемы анализа рекурсивных алгоритмов......Page 180 5.7. Сложность задач и нижние границы сложности......Page 187 5.8. Полиномиально разрешимые и труднорешаемые задачи......Page 190 5.9. Классы Р и NP......Page 191 5.10. NP-полные и NP-трудные задачи......Page 194 5.11. Подходы к решению труднорешаемых задач......Page 196 5.12. Приближенные алгоритмы......Page 197 5.13. Сильная NP-полнота и псевдополиномиальные алгоритмы......Page 199 5.14. Контрольные вопросы и упражнения......Page 202 Список литературы......Page 206 Предметный указатель......Page 208 Список алгоритмов......Page 210