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

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

Способы математического описания конечных автоматов

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

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

Таблица 1 является таблицей переходов полного синхронного автомата. Из таблицы видно, что автомат имеет четыре состояния входа p1, p2, p3, p4 и четыре внутренних состояния h1, h2, h3, h4. В каждой клетке таблицы указывается номер внутреннего состояния, в которое автомат должен перейти в следующий момент времени.

Если в какой-либо клетке таблицы состояние не указано, то это состояние называется неопределенным, а такой автомат называется недоопределенным.

Недоопределенные автоматы могут существовать только теоретически. Практически же любая реальная схема автомата, построенная из логических элементов, соответствует полностью определенному конечному автомату. Для задания функции выходов автомата в таблицу переходов добавляют дополнительный столбец (автомат Мили) или выходные состояния указываются дополнительно в каждой клетке таблицы (таблицы 2,3 соответственно).

 

Таблица.1 - Таблица переходов

Внутреннее состояние (до перехода)	Состояние автомата (после перехода) при установке состояний входа
p1	p2	p3	p4
h1	h1	h3	h2	h1
h2	h2	h1	h4	h2
h3	h3	h3	h3	h2
h4	h4	h1	h2	h4

 

Таблица 2 - Таблица переходов с дополнительным столбцом, указывающим функцию выхода

 

Внутреннее состояние (до перехода)	Состояние автомата (после перехода) при установке состояний входа	Функция выхода
p1	p2	p3	p4
h1	h1	h3	h2	h1	Y1
h2	h2	h1	h4	h2	Y2
h3	h3	h3	h3	h2	Y3
h4	h4	h1	h2	h4	Y4

 

Таблица 3 - Таблица переходов с указанием в каждой ячейке таблиц функции выхода после перехода

 

Внутреннее состояние (до перехода)	Состояние автомата (после перехода) при установке состояний входа
p1	p2	p3	p4
h1	h1/y1	h3/y2	h2/y1	h1/-
h2	h2/y3	h1/y1	h4/-	h2/-
h3	h4/-	h3/y4	h3/-	h2/y3
h4	h3/y4	h1/-	h2/y2	h4/y1

 

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

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

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

 

 

Таблица 4 - Таблица переходов с указанием устойчивых состояний асинхронного автомата

 

Внутреннее состояние (до перехода)	Состояние автомата (после перехода) при установке состояний входа
p1	p2	p3	p4
h1	(h1)	h3	h2	(h1)
h2	(h2)	h1	h4	(h2)
h3	h4	(h3)	(h3)	h2
h4	h3	h1	h2	(h4)

 

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

 

Таблица 5 - Матрица переходов автомата

 

Исходное внутренние состояние	Переход во внутренние состояния
h1	h2	h3	h4
При состояниях входа/выхода
h1	p1/y1	p2/y2	p4/y1	p3/y2
h2	p3/y2	p1/y4	p2/y3	p4/y2
h3	p3/y4	p1/y1	p2/y4	p4/y1
h4	p2/y3	p3/y3	p1/y2	p4/y1