Контрольная работа: Абстрактные цифровые автоматы

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

При аналитическом способе задания абстрактные автоматы задаются четверкой объектов:

S={ X,A,Y,F}, где F задает для каждого состояния аj автомата отображение (ХхА) - > (AxY). Другими словами, при аналитическом способе задания для каждого состояния автомата аj указывается отображение Fai, представляющее собой множество всех троек ар, xm, yk, и таких, что под воздействием входного сигнала xm автомат переходит из состояния аj в состояние ар, выдавая при этом выходной сигнал yk.

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

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

Fai{ap (Xm/yk),ai (Xf/yz) …}.

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

S={ X,A,Y,F}, X={x1,x2}, A={a1, а2, а3}, Y={y1, y2, у3},

Fa1={a2 (x1/y2), a1 (x2/у3) },

Fа2={а3 (x1/y3), a1 (x2/y1) },

Fa3={a1 (x1/y3), а2 (x2/y2) }.

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

Определим синхронные и асинхронные автоматы. Состояние аs автомата S называется устойчивым cостоянием, если для любого входного сигнала хjХ, такого, что аs= δ (аi Хm) имеет место as= δ (as, xm).

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

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

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

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

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

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

Так как  (a1, x1) = а3, a  (a1, x1) = y1, то под действием первой буквы слова Х входного сигнала x1 автомат перейдет в состояние a3 и на выходе его появится сигнал y1. Далее,  (а3, x1) = a1, а  (а3, x1) = у2, потому при приходе второго сигнала x1 автомат окажется в состоянии a1, а на выходе его появится сигнал у2. Проследив непосредственно по графу или таблицам переходов и выходов дальнейшее поведение автомата, опишем его тремя строчками, первая из которых соответствует входному слову X, вторая - последовательности состояний, которые проходит автомат под действием букв слова X, третья - выходному слову У, которое появляется на выходе автомата:

x1 x1 x2 x1 x2 x2

a1 а3 a1 a1 а3 a2 а3

y1 y2 y1 y1 y1 y2

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

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

Очевидно, что выходной сигнал уi1=λ (am) в момент времени i1 не зависит от входного сигнала xi1, а определяется только состоянием аm.

Таким образом, этот сигнал yi1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i1. В связи с этим под реакцией автомата Мура, установленного в состояние am на входное слово X=xi1, хi2,., хik будем понимать выходное слово той же длины у= λ (am, Х) =уi2, уi3,., yik+1.

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

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

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

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

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

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

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

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

ХA={х1, х2,. хn}; Y={y1, у2,. уm}; А={ а0, а1, а2,. аN}; а0A = а0 - начальное состояние (а0AА); A - функция переходов автомата, задающая отображение (ХAхАA) - >АA; A - функция выходов автомата, задающая отображение АA->УA.

Построим автомат Мили: SB={ ХB, АB, YB,B, B, а0B}, у которого АB=АA; ХB=ХA; YB=УA; B=A; а0B=а0A. Функцию выходов B определим следующим образом. Если в автомате Мура A (аm, х1) = аs и A (аs) =yg, то в автомате Мили B (am, х1) =yg

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

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

При табличном способе задания автомата таблица переходов автомата Мили совпадает с таблицей переходов исходного автомата Мура, а таблица выходов получается из таблицы переходов заменой символа as, стоящего на пересечении строки хf и столбца аm, символом выходного сигнала yg отмечающего столбец as в таблице переходов автомата SA.

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

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

SA={ ХA, АA,YA, A, A, a0A},

где:

ХA={x1, x2,. xn}; Y={y1, у2,. ym}; А={ a0,a1,a2,. aN}; a0A = a0 - начальное состояние (а0AА); A - функция переходов автомата, задающая отображение (ХAxАA) - >АA; A - функция выходов автомата, задающая отображение (ХAxАA) - >YA.

Построим автомат Мура: SB={XB, AB, YB, B, B, a0B}, у которого XB=XA; YB=YA.

Для определения AB каждому состоянию asАA поставим в соответствие множество As всевозможных пар вида (as, yg)

Функцию выходов B определим следующим образом. Каждому состоянию автомата Мура SB, представляющему собой пару вида (as,yg), поставим в соответствие выходной сигнал yg.

Если в автомате Мили SA был переход A (am, xf) = as и при этом выдавался выходной сигнал A (am,xf) =yg, то в SB будет переход из множества состояний Am, порождаемых am, в состояние (as,yg) под действием входного сигнала xf.

В качестве начального состояния a0B можно взять любое из состояний множества A0, которое порождается начальным состоянием a0 автомата SA. При этом выходной сигнал в момент времени t=0 не должен учитываться.

Рассмотрим пример. Пусть задан автомат Мили (табл.1.10.)

Поставим в соответствие каждой паре аi/xk состояние Ьik (i-номер состояния, k-номер входного сигнала), с учетом b0.

Составим таблицу переходов автомата Мура, руководствуясь следующими правилами:

1) Выпишем из таблицы 1.11 состояния автомата Мили и соответствующие каждому из них множества состояний автомата Мура (bik):

а0= {b0, b02, b11, b21}; a1= {b22}; а2= {b01, b12};

2) Если состояние автомата Мура bik входит в множество, соответствующее состоянию аp автомата Мили, то в строку таблицы переходов автомата Мура для состояния bik следует записать строку из таблицы переходов автомата Мили, соответствующую состоянию ар (из 1.10.).

3) Функцию выходов автомата Мура определим следующим образом: B (bik) =A (аi, xk). Для начального состояния b0 значение выходного сигнала можно выбрать произвольно, но порождаемый начальным состоянием a0 (с учетом понятия эквивалентности состояний). Результирующая таблица переходов и выходов автомата Мура эквивалентного автомату Мили, заданному таблицей 1.10 представлена в таблице 1.12.

4) Найдем в таблице 1.12 эквивалентные состояния и удалим их (заменим на представителя класса эквивалентности).

Если выходной сигнал возле b0 доопределить y1, то окажется, что в данной таблице переходов находится 3 эквивалентных состояния (b0,b11,b02). Заменив класс эквивалентности одним представителем (b0), получим окончательную таблицу переходов (табл.1.13).

Таблица 1.12

Таблица 1.13.

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

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

Алгоритм Ауфенкампа-Хона.

В основу метода минимизации состояний автомата положена идея разбиения всех состояний исходного, абстрактного автомата на попарно не пересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием (представителем данного класса). Образующийся в результате этих преобразований минимальный автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются исходные состояния.

Два состояния автомата am и as называются эквивалентными (am =as), если  (am,X) =  (as,X) для всех возможных входных слов длины X.

Если am и as не эквивалентны, они различимы. Более слабой эквивалентностью является K-эквивалентность. Состояния am и аs K-эквивалентны, если  (am, Хk) =  (as, Хk) для всех возможных входных слов длины К. При минимизации числа внутренних состояний автомата Мили S={X,Y, А, ,, а0} используется алгоритм Ауфенкампа-Хона:

1. Находят последовательные разбиения 1,2,…,k,k+1, множества А на классы одно-, двух-,., К-, (К+1) - эквивалентных состояний до тех пор, пока на каком-то (К+1) шаге не окажется, что k=k+1. В этом случае К-эквивалентные состояния являются эквивалентными. Число шагов К, при котором k=k+1 не превышает N-1, где N - число внутренних состояний автомата.

2. В каждом классе эквивалентности  выбирают по одному элементу (представителю класса), которые образуют множества А' состояний минимального автомата S'.

3. Функцию переходов ' и выходов ' автомата S' определяют на множестве A'xX.

Для этого в таблице переходов и выходов вычеркивают столбцы, соответствующие не вошедшим в множество А' состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества А', (на представителей).

4. В качестве а'0 выбирается одно из состояний, эквивалентное состоянию а0. В частности, удобно принять само состояние а0.

При минимизации автомата Мура вводится понятие 0-эквивалентности состояний и разбиения множества состояний на 0-классы: 0-эквивалентными называются любые, одинаково отмеченные выходными сигналами, состояния автомата Мура. В качестве примера рассмотрим минимизацию автомата Мура, заданного таблицей переходов и выходов (Таблица 1.14).

Таблица 1.14

Выполним разбиение 0:

0={В1, В2, В3};

B1={a1, a2, a8}, В2={а6, а9, а10, а11, а12}, В3={а3, a4, a5, a7}.

Построим таблицу разбиения 0:

Выполним разбиение 1:

1={С1, С2, С3, С4};

C1={a1, a2, a8}, С2={а6, а9, а11}, С3={ а10, a12}, С4={а3, а4, a5, a7}.

Построим таблицу разбиения 1:

Выполним разбиение 2.

1={D1, D2, D3, D4};

D1={a1, a2, a8}, D2={а6, а9, а11}, D3={ а10, a12}, D4={а3, а4, a5, a7}.

Разбиение 2 повторяет разбиение 1 - процедура разбиения завершена.

Выберем произвольно из каждого класса эквивалентности D1, D2, D3, D4 по одному представителю - в данном случае по минимальному номеру: A'={a1, а3, a6, а10}.

Удаляя из исходной таблицы переходов "лишние" состояния, определяем минимальный автомат Мура (табл.1.15.)

Таблица 1.15.

В процессе выполнения контрольной работы мы ознакомились с основными понятиями абстрактных цифровых автоматов; типами абстрактных автоматов; способами задания абстрактных автоматов; связью между моделями Мили и Мура; эквивалентными автоматами и эквивалентными преобразованиями автоматов; минимизацией числа внутренних состояний автомата и алгоритмом Ауфенкампа-Хона - привели примеры.

1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа" 1987.

2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.

3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.

4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.

5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.