Абстрактные цифровые автоматы (стр. 3 из 5)

Применительно к общему определению абстрактного автомата, последнее равнозначно описанию функций δи λв соответствии с выражением: a_p= δ (a_i, x_m), y_к= λ (a_i, x_m).

Отображение F_aiзаписывается следующим образом:

F_ai{a_p (X_m/y_k),a_i (X_f/y_z) …}.

Для абстрактного автомата Мили (табл.1.7.) аналитическое задание имеет следующий вид:

S={ X,A,Y,F}, X={x₁,x₂}, A={a₁, а₂, а₃}, Y={y₁, y₂, у₃},

F_a1={a₂ (x₁/y₂), a₁ (x₂/у₃) },

F_а2={а₃ (x₁/y₃), a₁ (x₂/y₁) },

F_a3={a₁ (x₁/y₃), а₂ (x₂/y₂) }.

Следует отметить, что функция F_ai всегда записывается для исходного состояния.

Определим синхронные и асинхронные автоматы. Состояние а_sавтомата Sназывается устойчивым cостоянием, если для любого входного сигнала х_j

Х, такого, что а_s= δ (а_iХ_m) имеет место a_s= δ (a_s, x_m).

Автомат S называется асинхронным, если каждое его состояние a_s

А устойчиво. Автомат S называется синхронным, если он не является асинхронным.

Необходимо заметить, что построенные на практике автоматы всегда асинхронные и устойчивость их состояний всегда обеспечивается тем или иным способом, например, введением сигналов синхронизации. Однако, на уровне абстрактной теории автоматов, когда автомат всего лишь математическая модель, которая не отражает многих конкретных особенностей его реализации, часто оказывается более удобным оперировать с синхронными автоматами.

1.4 Связь между моделями Мили и Мура

Как уже отмечалось, абстрактный автомат работает как преобразователь слов входного алфавита в слова выходного алфавита.

Пусть абстрактный автомат Мили задан графом рис.1.5.

На вход этого автомата, установленного в начальное состояние, поступает входное слово X=x₁, x₁, x₂, x₁, x₂, x₂.

Рисунок 1.5 - Граф автомата Мили

Так как  (a₁, x₁) = а₃, a (a₁, x₁) = y₁, то под действием первой буквы слова Х входного сигнала x₁ автомат перейдет в состояние a₃ и на выходе его появится сигнал y_1. Далее,  (а₃, x₁) = a₁, а  (а₃, x₁) = у₂, потому при приходе второго сигнала x₁ автомат окажется в состоянии a₁, а на выходе его появится сигнал у₂. Проследив непосредственно по графу или таблицам переходов и выходов дальнейшее поведение автомата, опишем его тремя строчками, первая из которых соответствует входному слову X, вторая - последовательности состояний, которые проходит автомат под действием букв слова X, третья - выходному слову У, которое появляется на выходе автомата:

x₁x₁ x₂x₁x₂x₂

a₁а₃ a₁a₁а₃a₂а₃

y₁y₂ y₁y₁y₁y₂

Назовем у = (а₁, X) реакцией автомата Мили в состоянии a₁ на входное слово X. Как видно из примера, в ответ на входное слово длины kавтомат Мили выдает последовательность состояний длины к+1 и выходное слово длины k. В общем виде поведение автомата Мили, установленного в состояние а_m, можно описать следующим образом:

Входное слово	xi1	xi2	xi3
Последовательность состояний	am	ai2= (am,xi1)	ai3= (ai2,xi2).
Выходное слово	yi1= (am,xi1)	yi2= (ai2,xi2)	yi3= (ai3,xi3)

Точно так же можно описать поведение автомата Мура, находящегося в состоянии a_m, при приходе входного слова x_i1, x_i2,., х_ik. Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t (У (t)) зависит лишь от состояния, в котором находится автомат в момент t (a (t)):

Входное слово	xi1	xi2	xi3
Последовательность состояний	am	ai2= (am,xi1)	ai3= (ai2,xi2)	ai4= (ai3,xi3)
Выходное слово	yi1= (am,xi1)	yi2= (ai2,xi2)	yi3= (ai3,xi3)	yi4= (ai4)

Очевидно, что выходной сигнал у_i1=λ (a_m) в момент времени i₁ не зависит от входного сигнала x_i1, а определяется только состоянием а_m.

Таким образом, этот сигнал y_i1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i₁. В связи с этим под реакцией автомата Мура, установленного в состояние a_mна входное слово X=x_i1, х_i2,., х_ikбудем понимать выходное слово той же длины у= λ (a_m,Х) =у_i2, у_i3,., y_ik+1.

В качестве примера рассмотрим автомат Мура S5, граф которого изображен на рис.1-6, и найдем его реакцию в начальном состоянии на то же самое входное слово которое мы использовали при анализе поведения автомата Мили S1:

Входное слово	x1	x1	x2	x1	x2	х2
Последовательность состояний	a1	a4	a1	a1	a4	a3	a5
Выходное слово	y1	y1	y2	y1	y1	y1	y2

Рисунок 1-6 - Граф автомата Мура

Как видно из этого и предыдущего примеров, реакции автоматов S5 и S1 в начальном состоянии на входное слово Х с точностью до сдвига на 1 такт совпадают (реакция автомата Мура обведена линией). Дадим теперь строгое определение эквивалентности полностью определенных автоматов.

Два автомата S_Aи S_Bс одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.

1.5 Эквивалентные автоматы. Эквивалентные преобразования автоматов

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

При описании алгоритмов взаимной трансформации автоматов Мили и Мура в соответствии с изложенным выше мы будем пренебрегать в автоматах Мура выходным сигналом, связанным с начальным состоянием ( (a₁)).

Рассмотрим сначала преобразование автомата Мура в автомат Мили.

Пусть дан автомат Мура: S_A={ Х_A, А_A, У_A,_A,_A, а_оA}, где:

Х_A={х₁, х₂,. х_n}; Y={y₁, у₂,. у_m}; А={ а₀, а₁, а₂,. а_N}; а_0A= а_{0 -} начальное состояние (а_0A

А); _A - функция переходов автомата, задающая отображение (Х_AхА_A) - >А_A; _A - функция выходов автомата, задающая отображение А_A->У_A.

Построим автомат Мили: S_B={ Х_B, А_B, Y_B,_B, _B, а_0B}, у которого А_B=А_A; Х_B=Х_A; Y_B=У_A; _B=_A; а_0B=а_0A. Функцию выходов _Bопределим следующим образом. Если в автомате Мура _A (а_m, х₁) = а_sи _A (а_s) =y_g, то в автомате Мили _B (a_m, х₁) =y_g

Рисунок 1.7 - Иллюстрация перехода от модели Мура к модели Мили

Переход от автомата Мура к автомату Мили при графическом способе задания иллюстрируется рис.1-7: выходной сигнал y_gзаписанный рядом с вершиной (a_s), переносится на все дуги, входящие в эту вершину.

При табличном способе задания автомата таблица переходов автомата Мили совпадает с таблицей переходов исходного автомата Мура, а таблица выходов получается из таблицы переходов заменой символа a_s, стоящего на пересечении строки х_fи столбца а_m, символом выходного сигнала y_gотмечающего столбец a_sв таблице переходов автомата S_A.

Из самого способа построения автомата Мили S_Bочевидно, что он эквивалентен автомату Мура S_A. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов S_Aи S_B, установленных в состояния a_m, вызовет появление одинаковых выходных слов и, следовательно, автоматы S_Aи S_Bэквивалентны.

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

S_A={ Х_A, А_A,Y_A, _A, _A, a_0A},

где:

Х_A={x₁, x₂,. x_n}; Y={y₁, у₂,. y_m}; А={ a₀,a₁,a₂,. a_N}; a_0A= a₀ - начальное состояние (а_0A

А); _A - функция переходов автомата, задающая отображение (Х_AxА_A) - >А_A; _A - функция выходов автомата, задающая отображение (Х_AxА_A) - >Y_A.