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

Таблицы переходов и выходов. При этом способе каждая функция – переходов и выходов – задается в виде таблицы, называемой, соответственно, таблицей переходов и таблицей выходов. Столбцы обеих таблиц соответствуют различным состояниям входа автомата (элементам множества {X}), строки обеих таблиц – внутренним состоянием автомата (элементам множества {S}).

На пересечении i-й строки и ј-го столбца таблицы переходов указывается то внутреннее состояние S(t+1), в которое автомат перейдет из внутреннего состояния s_{i ­} (i -я строка) под действием входных сигналов, соответствующих состоянию входа x­_ј (ј-й столбец).

Поскольку S(t+1) есть значение, которое принимает функция переходов φ при X(t)= x­_ј и S(t)= s_{i ­­}, то, следовательно, задание S(t+1) и есть задание функции φ. На пересечении i-й строки и ј-го столбца таблицы выходов указывается то состояние выхода Z(t), которое будет иметь место, если на автомат, находящийся в момент t во внутреннем состоянии S_i­, входной сигнал, соответствующий состоянию входа x­_ј­.

Поскольку Z(t), есть значение функции выходов f при S(t)= s_{i ­­} и X(t)= x­_ј, то, следовательно, задание Z(t) это и есть задание функции f. Часто внутренние состояния автомата обозначаются не символами s_i­, а просто цифрой i, соответствующей номеру внутреннего состояния (рисунок 7)

Рисунок 7 – Таблицы переходов и выходов

Таблицу переходов и выходов можно совместить в одну таблицу. Тогда записью в каждой клетке таблицы является значение функции φ­_{­ ­} в виде S(t+1), и f – в виде Z(t), которые отделяются друг от друга запятой

(рисунок 8)

Рисунок 8 – Совместная таблица переходов и выходов

Графы переходов и выходов. Граф переходов представляет собой некоторую структуру, состоящую из вершин, изображаемых кружками, и ориентированных (направленных) дуг, изображаемых в виде линий между парами вершин и снабженных стрелками, указывающими направление от одной вершины к другой. Каждая вершина графа переходов соответствует внутреннему состоянию, которое указывается внутри кружка. Направленные дуги, соединяющие две вершины i и j, отмечаются записью того состояния входа х_к, который вызвал переход автомата из состояния i в состояние j, а так же записью того состояния выхода z₁, которое имело место при этом. Такая двойная запись х_к, z₁ носит название пары «вход-выход». Например, если над дугой записано х_к, z₁,то это значит, что переход автомата в состояние j произошел под действием входного сигнала, соответствующего состоянию входа х_к, при этом сигнал на выходе принял значение z­₁. В общем случае переход из состояния i в j может происходить под действием различных входных сигналов; для обозначения этого используется знак дизъюнкции «V», которым связываются все пары вход-выход, соответствующие этому переходу. Например, (х₁/z₁)V(x₂/z₂)V…V(x_r/z_r). Граф переходов автомата приведен на рисунке 9.

Рисунок 9 – Задание автомата в виде графа

5.2 Способы задания асинхронного автомата

Для задания асинхронного автомата можно тоже использовать таблицы и графы. Как и в синхронном автомате, строки таблицы переходов соответствуют внутренним состояниям, а столбцы – состояниям входа автомата. На пересечении строки и столбца указывается состояние автомата: устойчивое – цифрой в кружке, неустойчивое, предшествующее данному устойчивому, – той же цифрой, но без кружка. Особенностью асинхронных автоматов является то, что одному и тому же внутреннему состоянию может соответствовать несколько устойчивых состояний.

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

Поясним рисунок 10, рассмотрев первую и вторую строки. Прежде всего, в таблице четыре строки, следовательно, автомат имеет четыре внутренних состояния: s­₁, s­₂, s₃, s₄, хотя устойчивых состояний у него шесть. В первой строке указано устойчивое состояние 1, которое имеет место, если автомат находится во внутреннем состоянии s­₁ и состояние входа есть x₁. Если происходит изменение состояния входа с x₁ на x₂, то, следуя по строке 1 и переходя к столбцу 2, видим, что там указано неустойчивое состояние 2. Значит, автомат из состояния 1 перейдет в неустойчивое состояние 2, а затем, поскольку состояние входа сохраняется равным x₂, перейдет в устойчивое состояние 2. Если затем произойдет изменение состояния входа с x₂ на x₃, то, двигаясь по второй строке таблицы до столбца x₃, видим, что там указано устойчивое состояние 6. Это значит, что при таком изменении входа автомат из устойчивого состояния 2 в устойчивое 6 перейдет непосредственно, без изменения его внутреннего состояния. Если теперь произойдет изменение состояния входа с x₃ на x₄, то из таблицы определяем, что автомат перейдет в неустойчивое состояние 4 (столбец x₄, вторая строка). Поскольку состояние входа x₄ сохраняется до конца изменений памяти автомата, то автомат достигает устойчивого состояния 4. Чтобы завершить задание автомата, необходимо задать его функцию выходов. С этой целью строится таблица выходов, которая имеет два столбца: столбец устойчивых состояний и столбец соответствующих им выходных сигналов. Иногда таблицы выходов и переходов совмещают.

Рисунок 10 – Таблица переходов и выходов асинхронного автомата

Граф переходов асинхронного автомата по построению не отличается от синхронного, вершины его соответствуют внутренним состояниям, а направленные дуги отличаются соответствующими парами вход-выход (рисунок 11)

Рисунок 11 – Задание асинхронного автомата в виде графа

Всем устойчивым состояниям автомата соответствуют вершины с замкнутыми петлями, отмеченными теми состояниями входа, при которых, при данном внутреннем состоянии автомат будет находиться в устойчивом состоянии. Например, вершина 2 имеет петлю, отмеченную парой x₂/z₁ и x₃/z₂, как видно из таблицы, это соответствует устойчивым состояниям 2 и 6, имеющим место при втором внутреннем состоянии автомата и соответственно состоянии входа x₂ и x_3­.