Графом называется непустое конечное множество узлов. Граф обычно представляется в наглядной форме, при этом вершины изображаются точками или кругами, которые помечаются с целью идентификации, а ветви изображаются линиями, соединяющими соответствующие узлы. Если каждой дуге приписано направление, то такой граф называется ориентированным. Данные представления полезны ввиду их наглядности. Вершины обычно соответствуют объектам некоторого вида (в цифровом автомате – внутренним состояниями), а дуги – физическим или логическим связями между ними.
Так как для задания цифрового автомата удобно использовать граф, то перейдем к его построению. Состояние устройства в графе будет соответствовать вершинам (узлам графа) - обозначено кружками и внутри проставлено буквенное обозначение состояния. Узлы соединяются дугами, которые показывают направление перехода.
На дугах записываются условия перехода, под действием которого он имеет место, и выходные сигналы, которые при этом должны быть сформированы. Так как переключение триггеров происходит либо по фронту, либо по срезу синхронизирующего сигнала, будем считать, что до наступления следующего активного уровня изменение выходных сигналов не происходит, а, следовательно, и значение выходных сигналов у1 … у6 не измениться.
Рисунок 3 – Цифровой автомат. Граф переходов
