Короткова М.А. Математическая теория автоматов

Учебное пособие. -М.: МИФИ, 2008 . 116 с. Распознано
Рассматриваются вопросы представления детерминированных функций k-значных логик, способы задания, анализа и синтеза автоматов. Рассмотрены также базовые понятия теории кодирования, включая вопросы распознавания кодов автоматами. Пособие предназначено для студентов, обучаемых по специальности «Прикладная математика и информатика» и изучающих курс «Математическая теория автоматов». Предлагаемое пособие будет полезно также студентам третьего курса факультета Кибернетики, изучающим математическую лингвистику и теорию автоматов. Пособие может быть рекомендовано всем интересующимся теорией автоматов.
Содержание (6 глав):Ошибка! Закладка не определена.
Предисловие
Детерминированные функции и способы их задания
Функции k-значной логики. Формулы и реализация функций формулами
Полнота системы функций
Ограниченно-детерминированные (автоматные) функции с операциями
Детерминированные функции
Задание детерминированных функций с помощью деревьев
Вес детерминированной функции
Ограниченно-детерминированные функции и способы их задания
Диаграммы для детерминированных функций
Вопросы и упражнения
Основные типы преобразующих автоматов
Автомат Мили
Метод Хафмена минимизации числа состояний автомата
Автоматы Мура
Частичные автоматы
Вопросы и упражнения
Синтез автоматов
Последовательные автоматные вычисления
Синхронные сети автоматов
Правильно построенные логические сети
Вопросы и упражнения
Языки и грамматики
Алфавит, слова, операции над словами
Языки. Операции над языками
Регулярные множества и регулярные выражения
Задание языков системами уравнений
Грамматики и их классификация
Вопросы и упражнения
А-языки и конечные лингвистические автоматы
Диаграмма грамматики
Порождение и распознавание цепочек
Детерминизация недетерминированных автоматов
Автоматы с лямбда-переходами
Соответствие между А-языками и регулярными выражениями
Минимизация числа состояний автомата
Разрешимые проблемы для А-грамматик
Вопросы и упражнения
Элементы теории кодирования
Основные понятия теории
Критерий однозначности кодирования
Коды с минимальной избыточностью
Самокорректирующиеся коды
Построение автоматов, распознающих префиксные коды
Вопросы и упражнения
Список литературы