СОДЕРЖАНИЕ
Введение
1. Абстрактный синтез конечного автомата
1.1 Формирование алфавитного оператора
1.2 Приведение оператора к автоматному виду
1.3 Построение графа переходов абстрактного автомата
1.4 Минимизация абстрактного автомата
2. Структурный синтез конечного автомата
2.1 Кодирование состояний, входных и выходных сигналов
2.2 Формирование функций возбуждения и выходных сигналов структурного автомата
Заключение
Список литературы
ВВЕДЕНИЕ
Теория автоматов – это теория, на которой основаны экспериментальные методы исследования в кибернетике. При подходе к теории автоматов, как к части теории алгоритмов, центральной проблемой является изучение возможностей автоматов в терминах множеств слов, с которыми работают автоматы.
Можно выделить два основных аспекта работы автомата.
1. Автоматы-распознаватели, которые распознают входные слова, т.е. отвечают на вопрос, принадлежит ли поданное на вход слово данному множеству.
2. Автоматы-преобразователи, которые преобразуют входные слова в выходные, т.е. реализуют автоматные отображения.
Одной из задач теории автоматов является задача описания автомата и его реализации, т.е. представления автомата как структуры, состоящей из объектов фиксированной сложности. В этом отношении теория автоматов оказалось наиболее развитой ветвью теории алгоритмов.
Общая теория автоматов подразделяется на абстрактную теорию и структурную теорию автоматов. Абстрактная теория автоматов занимает промежуточное положение между алгеброй и логикой. С точки зрения приложений значение абстрактной теории автоматов отнюдь не сводится к удовлетворению запросов одной лишь вычислительной техники. Современная теория автоматов представляет собой математический аппарат для решения широкого класса комбинаторных проблем.
Структурная теория автоматов позволяет реализовать абстрактный автомат на элементах, принадлежащих к заранее заданному классу.
Для преобразования дискретной информации в различных областях техники используются цифровые автоматы. К цифровым автоматам относятся отдельные узлы и блоки специализированных и универсальных ЦВМ и ЦВМ в целом. Цифровыми автоматами могут быть названы также устройства, в автоматике, телемеханике, радиолокации и других областях техники, в которых требуется выполнять преобразование над сигналами, представленные в дискретной (цифровой) форме.
Первое правило функционирования автоматов заключается в следующем. Автомат необязательно должен запоминать входные истории. Вполне достаточно, чтобы автомат запомнил класс эквивалентностей, к которому приходится данная история.
Второе правило функционирования автоматов состоит в том, что на один и тот же входной сигнал конечный автомат может реагировать по-разному, в зависимости от того, в каком состоянии он находится в настоящий момент.
Конечный автомат - это устройство, работающее в дискретные моменты времени, или такты. На вход конечного автомата в каждом такте поступает один из возможных входных сигналов, а на его выходе появляется выходной сигнал, являющийся функцией его текущего состояния и поступившего входного сигнала.
Внутренние состояния автомата также меняются. ............
