6

Лабораторная работа № 1 структурный синтез автомата мура

Цель работы: изучение синтеза конечного автомата Мура, заданного графом.

1Теоретические сведения

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

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

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

Определение: Состоянием автомата называется класс эквивалентности его входных историй.

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

Отличительной особенностью КА является скачкообразность перехода из одного состояния в другое.

В абстрактной теории автоматов обычно абстрагируются от конечной длительности переходных процессов реально существующих автоматов и рассматривают переход автоматов из одного состояния в другое как мгновенный, причем без каких-либо промежуточных состояний. При описании функционирования автоматов широко используется понятие абстрактного автоматного (дискретного) времени, принимающего целые неотрицательные значения: t = 0, 1, 2,..., n,... Каждому моменту дискретного времени ставится в соответствие то или иное состояние автомата, – важны лишь факты переключений, а не конкретные значения интервалов времени между ними. Чаще всего моменты изменения состояний автомата определяются специальным устройством – генератором импульсов синхронизации (такие автоматы называются синхронными). Если моменты переключения определяются моментом прихода входного сигнала, то автомат называется асинхронным.

Математической моделью реальных технических автоматов является абстрактный автомат. Абстрактный автомат представляется ”черным ящиком“ с одним входом X, одним выходом Y и множеством внутренних состояний А (рис.1.1).

Рисунок 1.1 Абстрактный автомат

Он задается шестью объектами:

• входным алфавитом X = x₁, x₂,..., x_k- входные сигналы;

• выходным алфавитом Y = y₁, y₂,..., y_p- выходные сигналы;

• множеством состояний автомата S = s₀, s₁,..., s_n-1;

• начальным состоянием автомата s₀S;

• функцией (s(t), x(t)) перехода автомата из одного состояния в другое;

• функцией (s(t), x(t)) выходов автомата.

В начальный дискретный момент времени t₀ автомат находится в состоянии s₀. В момент времени t абстрактный автомат способен принять входной сигнал x(t) и выдать выходной сигнал y(t). Абстрактный автомат можно рассматривать как устройство, отображающее множество слов входного алфавита X в множество слов выходного алфавита Y.

Закон функционирования абстрактного автомата может быть задан совокупностью уравнений:

(1.1)

Произвольные автоматы, описываемые выражениями (1.1), называют автоматами Мили. Частным случаем автомата Мили является автомат Мура, в функции выходов которого отсутствует непосредственная зависимость от входного сигнала x(t):

(1.2)

Возможно преобразование автомата Мили в автомат Мура и наоборот, но в общем случае автомат Мура имеет бóльшее число состояний, чем автомат Мили.

Выходные сигналы y(t) автомата Мура (1.2) зависят, но в неявном виде, от входных сигналов, поступивших на вход автомата в предшествующие дискретные моменты времени t = 0, 1, 2. Поведение автомата определяется не только моментом времени t, но и начальным состоянием s₀ автомата в момент t = 0. Состояние s(0) и выходной сигнал x(0) определяют, в соответствии с (1.2), состояние s(1) в дискретный момент времени t = 1. По s(1) и x(1) можно найти состояние автомата s(2) и выходной сигнал y(1) и так далее.

Автоматы могут быть инициальными и неинициальными. В инициальных автоматах начальное состояние фиксировано, т.е. они всегда начинают работать из одного и того же начального состояния a₀. Неинициальные автоматы могут начинать работу из любого состояния. В данной лабораторной работе изучается синтез инициального автомата Мура, начальное состояние которого обозначено через s₀.

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