Графический способ

Этот способ задания дискретных автоматов основан на использовании направленных графов.

Граф произвольного дискретного автомата представляет собой комбинацию вершин и ребер, изображаемых на рисунках кружочками и соединяющими их стрелками соответственно. Вершины отождествляются с состоянием автомата, а ребра – с входными сигналами. Если входной сигнал x_i вызывает переход автомата из состояния a_j в состояние a_k, то на графе автомата этому сигналу соответствует обозначенная буквой x_i стрелка, соединяющая вершину, соответствующую состоянию a_j, с вершиной, соответствующей состоянию a_k.

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

Для задания функции выходов автомата Мили ребра графа (стрелки) обозначаются не только входными, но и соответствующими им выходными сигналами. Если, например, обозначенная входным сигналом x_i стрелка соединяет вершину a_j с вершиной a_k, то ей приписывается выходной сигнал и она обозначается на графе x_i / z_m. Это означает, что если на автомат, находящийся в состоянии a_j, будет подан входной сигнал x_i, то на выходе появится выходной сигнал z_m и автомат перейдет в состояние a_k.

В случае автомата Мура, когда выходные сигналы зависят только от внутреннего состояния, в котором находится автомат, и не зависят от входных сигналов, принято обозначать выходными сигналами не ребра (стрелки), а вершины графа.

Таким образом, на графе автомата Мура каждая вершина имеет два обозначения: одно, показывающее состояние автомата, и другое – выходной сигнал, который отмечает данное состояние автомата независимо от того, каким путем (по какому ребру) пришел автомат в это состояние.

Рисунок 1.7

Рисунок 1.6

Примеры графов автоматов Мили и Мура приведены на рисунках 1.6 и 1.7 соответственно.

Граф автомата, благодаря введенным на нем обозначениям вершин и ребер, полностью задает автомат при условии, что каким-то образом, например, индексом a ₀, отмечена вершина графа, соответствующая начальному состоянию этого автомата.