- 30 %
Конечные автоматы и формальные языки: учебник

Автор: Алымова Е. В. , Деундяк В. М. , Пеленицын А. М.

Год: 2018

Издательство: Издательство Южного федерального университета

Место издания: Ростов-на-Дону|Таганрог

ISBN: 978-5-9275-2397-9

Страниц: 292

Форматы: PDF

цена:
350
245 руб.

Содержит полное и систематическое изложение материала, входящего в учебную программу курса «Теория конечных автоматов и формальных языков», изучаемых студентами специальности «Фундаментальная информатика и информационные технологии» Института математики, механики и компьютерных наук Южного федерального университета. Последовательно рассматриваются следующие темы: способы задания и распознавания формальных языков, регулярные языки, конечные автоматы, автоматы со спонтанными переходами, свойства регулярных языков, контекстно-свободные языки, нормальные формы контекстно-свободных языков, автоматы с магазинной памятью. Содержит упражнения и варианты индивидуальных заданий. Предназначен для студентов, которые обучаются по программам бакалавриата и магистратуры в области информационных технологий, прикладной математики и программирования.

Введение
Глава 1. Способы задания и распознавания формальных языков
§ 1.1. Алфавит и слова
§ 1.2. Языки и операции над языками
§ 1.3. Грамматики
§ 1.4. Классификация грамматик
§ 1.5. Распознаватели
§ 1.6. Упражнения
Глава 2. Регулярные языки
§ 2.1. Регулярные множества и регулярные выражения
§ 2.2. Уравнения и системы уравнений с регулярными коэффициентами
§ 2.3. Алгоритм решения систем с регулярными коэффициентами
§ 2.4. Совпадение классов регулярных и ПЛ-языков
§ 2.5. Упражнения
Глава 3. Конечные автоматы
§ 3.1. Определения и примеры
§ 3.2. Редукция НКА к ДКА
§ 3.3. Граф переходов
§ 3.4. Совпадение классов КА-, регулярных и ПЛ-языков
§ 3.5. Лемма о разрастании для регулярных языков
§ 3.6. Упражнения
Глава 4. Конечные автоматы со спонтанными переходами
§ 4.1. Определения и примеры
§ 4.2. Редукция ε-НКА к ДКА
§ 4.3. Преобразование регулярного выражения в автомат
§ 4.4. Построение ε-НКА по ПЛ-грамматике
§ 4.5. Вычисление языка ε-НКА
§ 4.6. Задача минимизации конечного автомата
§ 4.7. Упражнения
Глава 5. Булева алгебра регулярных языков
§ 5.1. Свойства регулярных языков
§ 5.2. Замкнутость относительно булевых операций
§ 5.3. Алгоритмические проблемы регулярных языков
§ 5.4. Упражнения
Глава 6. Контекстно-свободные языки
§ 6.1. Деревья выводов в КС-грамматиках
§ 6.2. Проблема непустоты и устранение бесполезных сим¬волов
§ 6.3. Построение приведенной КС-грамматики
§ 6.4. Упражнения
Глава 7. Нормальные формы КС-грамматик
§ 7.1. Нормальная форма Хомского
§ 7.2. Проблема принадлежности для КС-языков
§ 7.3. Матричный метод перехода к нормальной форме Грейбах
§ 7.4. Упражнения
Глава 8. Автоматы с магазинной памятью
§ 8.1. Определения и примеры
§ 8.2. Расширенный МП-автомат
§ 8.3. Автомат, допускающий слово опустошением магазина
§8.4. Эквивалентность МП-автоматов и КС-грамматик
§ 8.5. Детерминированный МП-автомат
§ 8.6. Упражнения
Список литературы
Приложения
Приложение A. Алгоритмы для контекстно-свободных грамматик
Приложение B. Задание к курсовой работе
Приложение C. Варианты заданий
Приложение D. Пример выполнения заданий курсовой работы

Все отзывы о книге

Чтобы оставить отзыв, зарегистрируйтесь или войдите