Понятие о конечных автоматах

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

Конечные автоматы отличаются от комбинационных устройств наличием памяти. Наиболее простыми элементарными конечными автоматами являются триггеры, имеющие всего два внутренних состояния. Более сложные конечные автоматы строятся из элементарных. Поэтому если N — число внутренних состояний автомата, а n — число триггеров входящих в этот автомат, то справедливо соотношение:

Внутреннее состояние конечного автомата удобно кодировать многоразрядными двоичными числами, каждый из битов которых соответствует состоянию (0 или 1) одного из триггеров, входящих в конечный автомат. Работу конечных автоматов описывают с помощью таблицы переходов, показывающей, как изменяется внутренне состояние автоматов под действием тех или иных входных сигналов. Иногда описывают работу автоматов с помощью направленных графов, вершинами которых являются состояния автоматов, а ветвями — переходы из одних состояний в другие под действием входных сигналов.

Построим для примера таблицу переходов для J-K триггера, обозначая входной сигнал двухзначным двоичным числом первый разряд которого — сигнал J, а нулевой — сигнал K.

Построим по этой таблице граф работы триггера:

Наиболее распространенными конечными автоматами являются сдвиговые регистры и счетчики.