Необходимо заметить, что построенные на практике автоматы всегда асинхронные и устойчивость их состояний всегда обеспечивается тем или иным способом, например, введением сигналов синхронизации. Однако, на уровне абстрактной теории автоматов, когда автомат всего лишь математическая модель, которая не отражает многих конкретных особенностей его реализации, часто оказывается более удобным оперировать с синхронными автоматами.
Входное слово
xi1
xi2
xi3
Последовательность состояний
am
ai2=? (am,xi1)
ai3=? (ai2,xi2).
Выходное слово
yi1=? (am,xi1)
yi2=? (ai2,xi2)
yi3=? (ai3,xi3)
Точно так же можно описать поведение автомата Мура, находящегося в состоянии am, при приходе входного слова xi1, xi2,., хik. Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t (У (t)) зависит лишь от состояния, в котором находится автомат в момент t (a (t)):
ai3=? (ai2,xi2)
ai4=? (ai3,xi3)
yi4=? (ai4)
Очевидно, что выходной сигнал уi1=л (am) в момент времени i1 не зависит от входного сигнала xi1, а определяется только состоянием аm.
Таким образом, этот сигнал yi1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i1. В связи с этим под реакцией автомата Мура, установленного в состояние am на входное слово X=xi1, хi2,., хik будем понимать выходное слово той же длины у= л (am, Х) =уi2, уi3,., yik+1.
В качестве примера рассмотрим автомат Мура S5, граф которого изображен на рис.1-6, и найдем его реакцию в начальном состоянии на то же самое входное слово которое мы использовали при анализе поведения автомата Мили S1:
x1
x2
х2
a1
a4
a3
a5
y1
y2
Рисунок 1-6 - Граф автомата Мура
Как видно из этого и предыдущего примеров, реакции автоматов S5 и S1 в начальном состоянии на входное слово Х с точностью до сдвига на 1 такт совпадают (реакция автомата Мура обведена линией). Дадим теперь строгое определение эквивалентности полностью определенных автоматов.
Два автомата SA и SB с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.
Таблица 10
Таблица 11
A
X
А
a0
a2/y1
a0/у1
b0
b01
a0/y1
b02
а2/y2
a0/y1 b11
b12
a0/y2
a1/y1
a2
b21
b22
Страницы: 1, 2, 3, 4