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

Таблицы переходов задают функцию перехода автомата. Каждый столбец таблицы соответствует внутреннему состоянию автомата, каждая строка -определенному состоянию входа. Клетка таблицы переходов соответствует состоянию автомата, определяющему внутреннее состояние, в которое автомат должен перейти в следующий момент времени. Таблица 5.1 является таблицей переходов полного синхронного автомата. Из таблицы видно, что автомат имеет четыре состояния входа p1, p2, p3, p4 и четыре внутренних состояния h1, h2, h3, h4. В каждой клетке таблицы указывается номер внутреннего состояния, в которое автомат должен перейти в следующий момент времени. Если в какой-либо клетке таблицы состояние не указано, то это состояние называется неопределенным, а такой автомат называется недоопределенным. Недоопределенные автоматы могут существовать только теоретически. Практически же любая реальная схема автомата, построенная из логических элементов, соответствует полностью определенному конечному автомату. Для задания функции выходов автомата в таблицу переходов добавляют дополнительный столбец (автомат Мили) или выходные состояния указываются дополнительно в каждой клетке таблицы (таблица 5.2).

 

Таблица.5.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

 

Таблица 5.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

 

Таблица 5.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

 

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

 

Таблица 5.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)