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

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

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

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

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

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

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