Раздел 2. Автоматные языки описания цифровых автоматов

Тема 2.1. Автоматные языки описания цифровых автоматов. Графы переходов,

таблицы переходов и выходов

Среди автоматных языков наиболее распространены таблицы, графы и матрицы переходов и выходов.

Рассмотрим примеры таблиц для автоматов Мили и Мура

Пример автомата Мили

Таблица переходов:						Таблица выходов:

На пересечении столбца и строки ставят: и .

Таблицы переходов и выходов могут быть объединены в единую совмещенную таблицу переходов и выходов:

Пример автомата Мура:

Автомат Мура задается одной отмеченной таблицей переходов:

Для не полностью определенных автоматов на месте неопределенных состояний и выходных сигналов ставятся прочерки (не в шапках таблиц, а внутри таблиц).

Граф автомата – это ориентированный граф, вершинам которого соответствуют состояния автомата, а дугам – переходы.

Дуге , направленной от вершины к вершине приписывается (в модели Мили) входной сигнал и выходной сигнал , либо ставится прочерк.

В модели Мура выходной сигнал приписывается вершине, т.е. состоянию .

Автоматы и , заданные выше в виде таблиц, задаются следующими графами:

Функции заключительного состояния и заключительного выхода

Расширим функции и , определив их на множестве пар:

(состояние, входное слово)

Обозначим: - -е входное слово длиной символов;

- слово длиной нуль (пустое слово);

- множество всех конечных входных слов ненулевой длины: .

Функция заключительного состояния: на множестве определяется следующим образом:

1. для всех ;

2.

1) , если определена для всех ; ;

2) не определена в противном случае.

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

Функция заключительного выхода .

Модель Мура:

	, для , если определена
	Не определена, если не определена

Модель Мили:

	, , если определена
	Не определена, если не определена

Функция заключительного выхода – это выходной сигнал, который появляется в результате действия последнего символа цепочки :

• в модели Мура – это выходной сигнал отмечающий заключительное состояние;

• в модели Мили – это выходной сигнал, появляющийся на переходе в заключительное состояние.

Пример для автомата (Мили) введенного ранее.

Найдем

Решение

Последний переход , поэтому .

Реакция автомата

Реакция автомата в состоянии на входное слово - это цепочка выходных символов (выходное слово) вырабатываемая автоматом.

Для модели Мили:

	Не определена, если не определена.
	иначе:

Для модели Мура:

	Не определена, если не определена
	иначе:

Обратим внимание, что выходной сигнал вырабатываемый автоматом Мура в состоянии не входит в цепочку , т.к. он не является следствием действия символа .

Под реакцией автомата Мура в состоянии на входное слово понимается выходное слово длины , но сдвинутое на 1 такт автоматного времени сравнительно с выходным словом автомата Мили.