Абстрактный синтез конечного автомата

Теория автоматов - это теория, на которой основаны экспериментальные методы исследования в кибернетике. При подходе к теории автоматов, как к части теории алгоритмов, центральной проблемой является изучение возможностей автоматов в терминах множеств слов, с которыми работают автоматы.

Можно выделить два основных аспекта работы автомата.

1. Автоматы-распознаватели, которые распознают входные слова, т.е. отвечают на вопрос, принадлежит ли поданное на вход слово данному множеству.

2. Автоматы-преобразователи, которые преобразуют входные слова в выходные, т.е. реализуют автоматные отображения.

Одной из задач теории автоматов является задача описания автомата и его реализации, т.е. представления автомата как структуры, состоящей из объектов фиксированной сложности. В этом отношении теория автоматов оказалось наиболее развитой ветвью теории алгоритмов.

Общая теория автоматов подразделяется на абстрактную теорию и структурную теорию автоматов. Абстрактная теория автоматов занимает промежуточное положение между алгеброй и логикой. С точки зрения приложений значение абстрактной теории автоматов отнюдь не сводится к удовлетворению запросов одной лишь вычислительной техники. Современная теория автоматов представляет собой математический аппарат для решения широкого класса комбинаторных проблем.

Структурная теория автоматов позволяет реализовать абстрактный автомат на элементах, принадлежащих к заранее заданному классу.

Для преобразования дискретной информации в различных областях техники используются цифровые автоматы. К цифровым автоматам относятся отдельные узлы и блоки специализированных и универсальных ЦВМ и ЦВМ в целом. Цифровыми автоматами могут быть названы также устройства, в автоматике, телемеханике, радиолокации и других областях техники, в которых требуется выполнять преобразование над сигналами, представленные в дискретной (цифровой) форме.

Первое правило функционирования автоматов заключается в следующем. Автомат необязательно должен запоминать входные истории. Вполне достаточно, чтобы автомат запомнил класс эквивалентностей, к которому приходится данная история.

Второе правило функционирования автоматов состоит в том, что на один и тот же входной сигнал конечный автомат может реагировать по-разному, в зависимости от того, в каком состоянии он находится в настоящий момент.

Конечный автомат - это устройство, работающее в дискретные моменты времени, или такты. На вход конечного автомата в каждом такте поступает один из возможных входных сигналов, а на его выходе появляется выходной сигнал, являющийся функцией его текущего состояния и поступившего входного сигнала.

Внутренние состояния автомата также меняются. Моменты срабатывания (такты), определяются либо принудительно тактирующими синхросигналами, либо асинхронно, наступлением внешнего события, то есть приходом сигнала.

Существует два вида реализации конечного автомата - аппаратная и программная. В первую очередь, реализация конечного автомата требует построения устройства памяти для запоминания текущего состояния автомата. Обычно используются двоичные элементы памяти, или триггеры, запоминающие значение одного двоичного разряда.

1. АБСТРАКТНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА

1.1 Формирование алфавитного оператора

Для того чтобы оператор преобразовался к автоматному виду, необходимо выполнение трех условий:

1. Любым двум одинаковым начальным отрезкам входных слов должны соответствовать одинаковые начальные отрезки выходных слов;

2. Длина входного слова должна равняться длине выходного слова;

3. Последний символ должен возвращать автомат в начальное состояние.

Данный оператор уже выровнен, так как длина каждого из входных слов равна длине соответствующего выходного слова. Каждому входному слову здесь сопоставляются не более одного выходного слова, поэтому оператор однозначен. Однако он не удовлетворяет условию полноты.

Таким образом, автоматный вид оператора примет, следующий вид:

Таблица 2. Автоматный вид

1.3 Построение графа переходов абстрактного автомата

Построим по таблице 2 граф переходов автомата. При этом предполагается, что последний символ каждого входного слова должен переводит автомат в начальное состояние.

Граф переходов абстрактного автомата представлен в приложении 1.

1.4 Минимизация абстрактного автомата

2.1 Кодирование состояний, входных и выходных сигналов

Для кодирования состояний, входных и выходных сигналов конечного автомата, необходимо вычислить число элементов памяти:

а) рассчитаем число элементов памяти: Н = ] log₂h [, где h - число состояний после минимизации D = {}

H = ] log₂ 12 [ = 4

б) рассчитаем число входных (L) и выходных (М) шин:
L = ] log₂n[

М =] log₂m [,

где n, m - число букв входного и выходного алфавитов

Z = {0, 1} L = ] log₂ 2 [ = 1

W = {0, 1} M = ] log₂ 2 [ = 1

Из приведённого выше следует, что для кодирования состояний необходимо 4 элемента памяти, обозначим их Q₀, …, Q₃. Закодируем состояния (таблица 5) случайными кодами.

Таблица 5. Таблица кодированных состояний

2.2 Формирование функций возбуждения и выходных сигналов структурного автомата