Связь между математическими моделями цифровых автоматов Мили и Мура

Абстрактный цифровой автомат работает как преобразователь слов входного алфавита в слово в выходном алфавите [5]. Рассмотрим это положение, взяв в качестве примера автомат Мили S1.

На вход этого автомата, установленного в начальное состояние a1, поступает шестибуквенное (шеститактное) слово ξ=z1z1z2z1z2z2.

Проследив по таблицам переходов и выходов или непосредственно по графу поведение цифрового автомата S1, опишем его тремя строками, первая из которых соответствует входному слову ξ, вторая – последовательности соответствующих этому слову состояний β, третья – выходному слову ω, которое появляется на выходе автомата.

ω = λ(a1, ξ) – реакция автомата Мили в состоянии a1 на входное слово ξ.

Как видно из этого примера, в ответ на входное слово длиной k символов автомат Мили S1 выдаёт последовательность состояний длины k+1 символов и выходное слово длиной k символов.

В общем виде поведение автомата Мили, установленного в состояние am, можно описать следующим образом:

Точно так же описывается поведение автомата Мура, находящегося в состоянии am, при приходе входного слова zi1, zi2, ... , zik. Учитывая, что выходной сигнал автомата Мура в момент времени t, то есть w(t), зависит лишь от состояния, в котором находится автомат в момент t, то есть от a(t), получим:

Выходной сигнал wi1=λ(am) в момент времени i1 не зависит от входного сигнала zi1, а определяется только состоянием am. Таким образом, выходной сигнал wi1 не связан с входным словом, поступающим на вход автомата, начиная с момента i1.

По этой причине реакцией автомата Мура, установленного в состояние am, на входное слово ξ = zi1, zi2, ... , zik является выходное слово той же длины k, с исключением первого символа выходного слова:

ω = λ(am, ξ) = wi2, wi3, ... , wi(k+1).

В качестве примера рассмотрим автомат Мура S5, граф которого изображён на рис. 26, и определим его реакцию в начальном состоянии a1на то же самое слово ξ=z1z1z2z1z2z2 ,которое использовалось для оценки поведения автомата Мили S1:

Часть выходного слова, выделенная штриховой рамкой, является реакцией автомата Мура на входное слово.

Таким образом, реакции автоматов S5 и S1 в начальном состоянии на входное слово ξ с точностью до сдвига на один такт совпадают. Эти автоматы являются эквивалентными.

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

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