Электронные промышленные устройства. Кузнецов Б.Ф. - 88 стр.

88

      В табл. 2.6 возможные состояния в виде упорядоченной последовательности записаны в
первой строке, сигналы в упорядоченном виде – в первом столбце. На пересечении строк и столб-
цов получаем клетку, в которой записано новое состояние. Таблица переходов может быть опреде-
лена не полностью (прочерки в отдельных клетках). Некоторые сигналы не вызывают изменения
состояния. Так, под действием    автомат сохраняет состояние . Множество выходов подобным
образом задается для каждой пары f ai ; x j g; на пересечении соответствующих строки и столбца
получаем выходной сигнал автомата (см. табл. 2.5). Эта таблица также может быть не полностью
определенной. Иногда обе таблицы совмещают, тогда в каждой клетке записана пара f ai ; zj g.
      У автомата Мура таблица выходов 2.6 вырождается в одну строку, которую можно дописать
к первой строке таблицы переходов. Получим отмеченную таблицу переходов, которая полностью
характеризует автомат Мура (табл. 2.7). Табличное описание служит удобным формализован-
ным языком, на котором устанавливается взаимопонимание между заказчиком и разработчи-
ком.
      Автоматы Мура и Мили можно описать направленными графами. Вершины графа соответ-
ствуют состояниям автомата, дуги - переходам. Таким образом, граф полно и однозначно отобра-
жает таблицу переходов.
Табл. 2.7 Таблица состояний автомата Мура




                            —                                                             —


       Для автомата Мура выходы однозначно определяются его состояниями, поэтому они могут
быть указаны в вершинах графа, для автомата Мили — у концов дуг, так как выходы здесь зависят
как от входов, так и от состояний. Графы автоматов Мили (рис. 2.60,а) и Мура (рис. 2.60,6) соот-
ветствуют фрагментам табл. 2.5-2.7.




                           Рис. 2.60. Графы автоматов: а - Мили; б — Мура

      Распространенное средство описания автомата — граф-схема алгоритма ГСА (рис. 2.61). На
граф-схеме можно выделить четыре типа вершин: начальную, конечную, операторную и условную.
        Правила соединения вершин. Начальная вершина имеет единственный выход, конечная
– только вход, не обязательно единственный. Для остальных вершин: каждая вершина имеет вход,
не обязательно единственный, условная имеет два выхода, операторная — один выход. Каждый
выход вершины любого типа связан только с одним входом (однозначность определения пути на
ГСА). Любая вершина должна лежать на одном пути из начальной в конечную вершину. Один из
выходов условной вершины может соединяться с се входом. Такая вершина носит характер за-
держки, которая заканчивается в момент выполнения условия. В каждой условной вершине
можно записать одно из слов, представляющих собой минтерм, т. с. набор x~1 ; x~2 ; : : : ; x~N или, в
случае если некоторые условия несущественны, группу минтермов. При этом число букв в конъ-
юнкции уменьшается, а набор покрывает группу минтермов, т. е. клеток карты Карно. В данном
примере рис 2.60 наборы покрывают половину клеток, так как условие задано единственной пере-
менной.