Сучкова Л.И. Абстрактный и структурный синтез автоматов
Подождите немного. Документ загружается.
41
Рисунок 3.3
Тогда звездочки нужно заменить на единицы, которые и
станут результатом вычисления функции. Если в состоянии
а
1
на ленте нет еще одной единицы для стирания, то это оз-
начает, что число х является нечетным, и машина Тьюринга
должна зациклиться.
3.2 Автоматы Мили и Мура
3.2.1 Определение и способы задания автоматов Мили и
Мура
Автоматы Мили и автоматы Мура являются автомата-
ми-преобразователями и названы по имени американских
ученых, которые впервые начали их изучать.
Закон функционирования автоматов Мили описывается
следующими выражениями для функции переходов и функ-
ции выходов:
a (t + 1) = δ[a(t),z(t)]
w (t) = λ[a(t),z(t)]
42
Для автоматов Мура справедливы уравнения вида:
a(t + 1) = δ[a(t),z(t)]
w(t) = λ[a(t)]
В данных уравнениях a (t) – состояние автомата в
момент времени t, z(t) и w (t) – входной и выходной сигналы
в момент t, δ[a(t),z(t)] – функция переходов автомата,
λ[a(t),z(t)] или λ[a(t)] – функция выходов автомата.
Отличительной особенностью автоматов Мили является
то, что их выходные сигналы зависят как от состояния авто-
мата, так
и от значения входного сигнала. В автоматах Мура
выходные сигналы w(t) в каждый дискретный момент време-
ни t однозначно определяются состоянием автомата в тот же
момент времени и не зависят от значения входного сигнала.
Для полного задания автомата Мили или Мура дополни-
тельно к законам функционирования, необходимо указать их
начальное состояние и
определить входной и выходной ал-
фавиты.
При табличном способе задания автомат Мили описыва-
ется с помощью двух таблиц. Таблица переходов задает
функцию δ (таблица 3.1), таблица выходов - функцию λ (таб-
лица 3.2).
Таблица 3.1 – Таблица переходов автомата Мили
Таблица 3.2 – Таблица выходов автомата Мили
43
Каждому столбцу поставлено в соответствие одно со-
стояние из множества А, каждой строке - один входной сиг-
нал из множества Z. На пересечении столбца и строки запи-
сывается состояние, в которое должен перейти автомат из
состояния в столбце под действием входного сигнала в стро-
ке. На пересечении столбца a
m
и строки z
f
в таблице 3.2 за-
писывается выходной сигнал w
g
, выдаваемый автоматом в
состоянии a
m
при поступлении на вход сигнала z
f
.
Автомат Мили может быть задан одной совмещенной
таблицей переходов и выходов (таблица 3.3), в которой
каждый элемент a
s
/ w
g
записанный на пересечении столбца
a
m
и строки z
f
, определяется следующим образом:
a
s
=δ(a
m
, z
f
); w
g
=λ(a
m
, z
f
).
Таблица 3.3 – Совмещённая таблица переходов и выхо-
дов для автомата Мили
Автомат Мура задается одной отмеченной таблицей пе-
реходов (таблица 3.4), в которой каждому столбцу припи-
саны не только состояние a
m
, но еще и выходной сигнал w
g
,
соответствующий этому состоянию, где w
g
=λ(a
m
).
Таблица3.4 – Отмеченная таблица переходов автома-
та Мура
w
1
w
2
w
3
w
1
a
1
a
2
a
3
a
4
44
Для частичных автоматов Мили и Мура в рассмотрен-
ных таблицах на месте не определенных состояний и выход-
ных сигналов ставится прочерк. В таких автоматах выходной
сигнал на каком-либо переходе всегда не определен, если
неопределенным является состояние перехода. Кроме того,
выходной сигнал может быть неопределенным и для некото-
рых существующих
переходов.
При графическом способе автомат задается в виде ори-
ентированного графа, вершины которого соответствуют со-
стояниям, а дуги - переходам между ними. Дуга, направлен-
ная из вершины a
m
, задает переход в автомате из состояния
a
m
в состояние a
s
. В начале этой дуги записывается входной
сигнал
z
f
∈Z, вызывающий данный переход a
s
=δ(a
m
,z
f
). Для
графа автомата Мили выходной сигнал
w
g
∈W, формируемый
на переходе, записывается в конце дуги, а для автомата
Мура - рядом с вершиной a
m
, отмеченной состоянием a
m
, в
котором он формируется. Если переход в автомате из со-
стояния a
m
в состояние a
s
производится под действием не-
скольких входных сигналов, то дуге графа, направленной из
a
m
в a
s
, приписываются
все эти входные и соответствую-
щие выходные сигналы. Графы автоматов, заданных своими
таблицами переходов и выходов представлены на рисунках
3.4 и 3.5.
z
1
a
1
a
2
a
2
a
3
z
2
a
2
a
3
a
4
a
1
45
Рисунок 3.4 – Автомат Мили
Рассмотрим пример построения автомата Мили. Пусть
автомат «Продавец газет» может принимать монеты досто-
инством в 1 рубль и 2 рубля. Если сумма монет равна 3 руб-
лям, то автомат выдает газету. Если сумма больше 3 рублей,
то автомат возвращает все деньги.
46
Рисунок 3.5 – Автомат Мура
Введем обозначения входных и выходных символов и
состояний автомата.
Входные символы:
z1
- опущена монета достоинством 1 рубль;
z2
- опущена монета достоинством 2 рубля.
Выходные символы:
w
1
- сообщение "Принята сумма 1 руб.";
w
2
- сообщение "Принята сумма 2 руб.";
w
3
- выдача газеты;
w
4
- возврат денег.
Состояния автомата
:
a0
- принята сумма 0 руб. (начальное состояние);
a1
- принята сумма 1 рубль;
a2
- принята сумма 2 рубля.
Гр
а
привед
е
По
к
вивале
н
3.2
Ра
с
Мура
и
автома
т
выходо
в
и 3.6.
Таблиц
а
а
ф автомат
е
н на рисун
к
Рисунок 3
к
ажем, что
н
тный авто
м
.2 Преобра
з
с
смотрим п
и
обратно с
т
ов. Рассмо
т
в
которого
а
3.5 – Та
б
4
а Мили, у
п
к
е 3.6.
.6 – Автом
а
для автом
а
м
ат Мура и
н
з
ования авт
о
реобразова
н
точки зре
н
т
рим автом
а
приведены
б
лица пере
4
7
п
равляюще
г
а
т Мили «
Пр
а
та Мили м
н
аоборот.
о
матов Ми
л
н
ие автома
т
н
ия получ
е
а
т Мили, т
а
соответств
е
ходов авт
о
г
о продаж
е
Пр
одавец га
з
ожно пост
р
л
и и Мура
т
а Мили в
е
ния эквив
а
а
блица пер
е
е
нно в таб
л
о
мата Мил
и
е
й газет,
з
ет»
р
оить эк-
автомат
а
лентных
е
ходов и
л
ицах 3.5
и
48
Таблица 3.6 – Таблица выходов автомата Мили
Подадим на вход автомата, установленного в состояние
а
1
, входное слово ξ=z
1
z
2
z
2
z
1
z
2
z
2
. В таблице 3.7 приведена
последовательность состояний, которые автомат проходит
при обработке входного слова ξ, и выходные сигналы, фор-
мируемые при этих переходах.
Таблица 3.7
Назовем выходное слово ω = λ (a
1,
ξ) реакцией автомата
Мили в состоянии а
1
на входное слово ξ. В нашем случае ω =
w
2
w
1
w
2
w
2
w
1
w
2
. В ответ на входное слово длины k авто-
мат Мили выдаст последовательность состояний длины k+1 и
выходное слово длины k.
Аналогично можно описать поведение автомата Мура,
находящегося в состоянии a
1
, при приходе входного слова ξ
= z
i1
, z
i2
, . . . ,z
ik
учитывая, что w(t) = λ(a(t)). Очевидно, что
для автомата Мура выходной сигнал w
i1
= λ(a
m
) в момент
времени i
1
не зависит от входного сигнала z
i1
и определяется
только состоянием a
m
. Следовательно, сигнал w
i1
никак не
связан с входным словом ξ. В связи с этим под реакцией ав-
Последовательность
состояний
a
1
a
2
a
1
a
3
a
3
a
1
a
3
Входное слово ξ
z
1
z
2
z
2
z
1
z
2
z
2
Выходное слово ω w
2
w
1
w
2
w
2
w
1
w
2
49
томата Мура, установленного в состояние a
m
, на входное
слово ξ = z
i1
, z
i2
, . . . , z
ik
будем понимать выходное слово
той же длины ω = λ(a
m
, ξ) = w
i2
w
i3
...w
ik+1
, сдвинутое по от-
ношению к ξ
на один такт.
Рассмотрим пример. Пусть автомат Мура задан отме-
ченной таблицей переходов (таблица 3.8).
Таблица 3.8–Отмеченная таблица переходов автомата
Мура
w
1
w
2
w
3
w
2
a
1
a
2
a
3
a
4
Z
1
a
2
a
3
a
4
a
4
Z
1
a
4
a
1
a
1
a
1
Подадим на вход этого автомата ту же последователь-
ность ξ, что и для автомата Мили. Последовательность сме-
ны состояний и вырабатываемых выходных сигналов пред-
ставлена в таблице 3.9.
Таблица 3.9 – Реакция автомата Мура
Последовательность
состояний
a
1
a
2
a
1
a
4
a
4
a
1
a
4
Входное слово ξ
z
1
z
2
z
2
z
1
z
2
z
2
z
Выходное слово ω
w
1
w
2
w
1
w
2
w
2
w
1
w
2
Сравнив реакции автомата Мили и автомата Мура на
одно и то же слово ξ, можно сделать вывод, что эти реакции
50
совпадают. Следовательно, автоматы Мили и Мура реали-
зуют одно и то же преобразование слов входного алфавита.
Такие автоматы называются эквивалентными.
Определение. Два автомата с одинаковыми входными и
выходными алфавитами называются эквивалентными, если
после установки их в начальное состояние их реакции на
любое входное слово совпадают.
Для каждого автомата Мили может быть
построен эк-
вивалентный ему автомат Мура и наоборот.
Переход от автомата Мура к эквивалентному ему
автомату Мили осуществляется просто при графическом
способе задания автомата. Для получения графа автомата
Мили по графу автомата Мура необходимо выходной сигнал
w
g
, записанный рядом с вершиной a
s
исходного автомата
Мура, перенести на все дуги, входящие в эту вершину. В эк-
вивалентном автомате Мили количество состояний такое же,
как и в исходном автомате Мура.
При переходе от автомата Мили к эквивалентному
ему автомату Мура каждое состояние a
i
исходного автома-
та Мили порождает столько
состояний автомата Мура,
сколько различных выходных сигналов вырабатывается в
исходном автомате Мили при попадании в состояние a
i
. Рас-
смотрим переход от автомата Мили (назовем его автомат А)
на рисунке 3.7 к эквивалентному автомату Мура.