Читайте также:
|
|
Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними.
Рис. 3 Граф автомата Мили S1 Рис. 4 Граф автомата Мили S2
Две вершины графа автомата аm и аs (исходное состояние и состояние перехода) соединяются дугой, направленной от аm к аs, если в автомате имеется переход из аm в аs, т. е. если аs = (аm, zf) при некотором zf Î Z. Дуге (аm, аs) графа автомата приписывается входной сигнал zf и выходной сигнал wg = (аm, zf), если он определен, и ставится прочерк в противном случае. Если переход автомата из состояния аm в состояние аs происходит под действием нескольких входных сигналов, то дуге (аm - аs) приписываются все эти входные и соответствующие выходные сигналы. При описании автомата Мура в виде графа выходной сигнал wg = (аm) записывается внутри вершины или рядом с ней. На рис. 3, 4 и 5 приведены заданные ранее таблицами графы автоматов S1, S2, S3.
Рис. 5. Граф автомата Мили S3
В данной работе рассматриваются только детерминированные автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к графическому способу задания автомата это означает, что в графе автомата из любой вершины не могут выходить две и более дуги, отмеченные одним и тем же входным сигналом. Аналогично этому в матрице соединений автомата в каждой строке любой входной сигнал не должен встречаться более одного раза.
Табл. 9
Отмеченная таблица переходов асинхронного
автомата Мура S4
В заключение данного параграфа определим синхронные и асинхронные автоматы. Состояние аs автомата S называется устойчивым состоянием, если для любого входа zf Î Z, имеет место (аm, zf) = аs.
Автомат S называется асинхронным, если каждое его состояние as Î A устойчиво. Автомат S называется синхронным, если он не является асинхронным. Необходимо заметить, что построенные на практике автоматы - всегда асинхронные и устойчивость их состоянии всегда обеспечивается тем или иным способом, например введением сигналов синхронизации.
Рис. 6. Граф асинхронного автомата Мура S4
Однако на уровне абстрактной теории, когда автомат есть лишь математическая модель, которая не отражает многих конкретных особенностей его возможной реализации, часто оказывается более удобным оперировать с синхронными автоматами, что мы и будем делать на протяжении всей данной главы. Пример асинхронного автомата Мура S4 приведен в Табл. 9 и на Рис. 6. Нетрудно видеть, что все его состояния устойчивы.
Очевидно, что если в таблице переходов асинхронного автомата некоторое состояние аs стоит на пересечении строки zf и столбца аm (m<>s), то это состояние аs обязательно должно встретиться в этой же строке в столбце аs. В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине as, должна быть петля, отмеченная символами тех же входных сигналов. Анализ таблиц 3, 5 и 8 или рис. 3 - 5 показывает, что автоматы S1, S2 и S3 являются синхронными.
Дата добавления: 2015-08-03; просмотров: 96 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Табличный метод | | | Связь между моделями Мили и Мура |