Каким образом в общем виде описывается поведение автомата Мили?

Пример общего описания автоматов Мили таблицами переходов и выходов дан в табл. 14 и табл. 15. Строки этих таблиц соответствуют входным сигналам множества X, а столбцы – состояниям A, причём крайний левый столбец обозначен как начальное состояние инициального цифрового автомата a1. На пересечении столбца am и строки zf в таблице переходов ставится состояние as=δ(am, zf), в которое автомат переходит из состояния am под действием сигнала zf. В таблице выходов – соответствующий этому переходу выходной сигнал wg=λ(am, zf).

Пример табличного описания полностью определённого цифрового автомата Мили S1с тремя состояниями, двумя входными и двумя выходными сигналами приведён в табл. 16 и табл. 17.

Заголовочная строка и столбец обозначены одинаково для обеих таблиц, поэтому для экономии времени можно производить описание автомата Мили одной совмещённой таблицей переходов и выходов, например, табл. 18.

Для частичных автоматов, у которых функции δ и λ определены не для всех пар (am, zf)⊆ A×X, на месте неопределённых состояний и неопределённых выходных сигналов ставится какой либо специальный символ, например, прочерк. Пример табличного описания частичного автомата приведён в совмещённой табл. 19.

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

Две вершины графа автомата am и as (исходное состояние и состояние перехода) соединяются дугой, направленной от am к as , если в автомате имеется переход из am в as , то есть если as = δ(am, zf) при некотором zf ∈X. Дуге (am, as) графа автомата приписывается входной сигнал zf и выходной сигнал wg = λ(am, zf), если он определён, и ставится прочерк в противном случае. Если переход автомата из состояния am в состояние as происходит под действием нескольких входных сигналов, то дуге (am, as) приписываются все эти входные и соответствующие выходные сигналы.

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

Дата добавления: 2015-07-26; просмотров: 303; Нарушение авторских прав

Мы поможем в написании ваших работ!