Графический метод. Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними

Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними.

Рис. 3 Граф автомата Мили S₁ Рис. 4 Граф автомата Мили S₂

Две вершины графа автомата а_m и а_s (исходное состояние и состояние перехода) соединяются дугой, направленной от аm к аs, если в автомате имеется переход из а_m в а_s, т. е. если а_s = (а_m, z_f) при некотором z_f Î Z. Дуге (а_m, а_s) графа автомата приписывается входной сигнал z_f и выходной сигнал w_g = (а_m, z_f), если он определен, и ставится прочерк в противном случае. Если переход автомата из состояния а_m в состояние а_s происходит под действием нескольких входных сигналов, то дуге (а_m - а_s) приписываются все эти входные и соответствующие выходные сигналы. При описании автомата Мура в виде графа выходной сигнал w_g = (а_m) записывается внутри вершины или рядом с ней. На рис. 3, 4 и 5 приведены заданные ранее таблицами графы автоматов S₁, S₂, S₃.

Рис. 5. Граф автомата Мили S₃

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

Табл. 9

Отмеченная таблица переходов асинхронного

автомата Мура S₄

В заключение данного параграфа определим синхронные и асинхронные автоматы. Состояние а_s автомата S называется устойчивым состоянием, если для любого входа z_f Î Z, имеет место (а_m, z_f) = а_s.

Автомат S называется асинхронным, если каждое его состояние a_s Î A устойчиво. Автомат S называется синхронным, если он не является асинхронным. Необходимо заметить, что построенные на практике автоматы - всегда асинхронные и устойчивость их состоянии всегда обеспечивается тем или иным способом, например введением сигналов синхронизации.

Рис. 6. Граф асинхронного автомата Мура S4

Однако на уровне абстрактной теории, когда автомат есть лишь математическая модель, которая не отражает многих конкретных особенностей его возможной реализации, часто оказывается более удобным оперировать с синхронными автоматами, что мы и будем делать на протяжении всей данной главы. Пример асинхронного автомата Мура S₄ приведен в Табл. 9 и на Рис. 6. Нетрудно видеть, что все его состояния устойчивы.

Очевидно, что если в таблице переходов асинхронного автомата некоторое состояние аs стоит на пересечении строки z_f и столбца а_m (m<>s), то это состояние а_s обязательно должно встретиться в этой же строке в столбце а_s. В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине a_s, должна быть петля, отмеченная символами тех же входных сигналов. Анализ таблиц 3, 5 и 8 или рис. 3 - 5 показывает, что автоматы S₁, S₂ и S₃ являются синхронными.