СПб.: СПб ГТУРП, 2013. — 136 сУчебное пособие посвящено изложению теории конечных автоматов и применению её методов для проектирования управляющих устройств и программ. Предназначено для самостоятельной работы студентов по дисциплине «Дискретная математика» направления «Прикладная математика и информатика» 010400.62 СПб ГТУРП очной формы обучения.Содержание
Конечные автоматы
Введение
Теория конечных автоматов
Автомат без выходного преобразователя
Автомат с выходным преобразователем
Эквивалентность автоматов Мили и Мура
Канонический метод синтеза конечных автоматов
Абстрактный синтез конечных автоматов
Минимизация числа состояний полностью определенного автомата
Минимизация числа состояний частичного автомата
Структурный этап синтеза конечного автомата
Типы элементов памяти
Пример структурного синтеза синхронного автомата
Кодирование состояний синхронного автомата
Структура автомата с дешифратором
Построение комбинационной схемы автомата на ПЗУ и ПЛМ
Синтез микропрограммного автомата
Построение графа автомата Мура по ГСА
Построение не полностью определенного автомата
Асинхронный автомат
Синтез асинхронного автомата
Состязание элементов памяти
Кодирование состояний аснхронного автомата
Синтез схем элементов памяти
Исключение состязаний элементов памяти в синхронном автомате
Построение комбинационной схемы асинхронного автомата
Автоматы, формальные языки и грамматики
Основные определенния
Классификация грамматик по Хомскому
Примеры построения грамматик
Соответствие конечных автоматов и автоматных грамматик
Недетерминированные конечные автоматы
Преобразование некоторых типов грамматики к автоматному виду
Построение распознавателей и преобразователей, выполняющих синтаксический разбор
Библиографический список
