Автоматов

Граф переходов представляет собой структуру, состоящую из вершин, изображаемых в виде малых кружков, и ориентированных дуг, изображаемых в виде линий между парами вершин и снабженных стрелками, указывающими направление от одной вершины к другой. Граф переходов, описывающий автомат с состояниями, содержит вершин, причем каждая вершина соответствует одному состоянию автомата; состояние, изображаемое вершиной, снабжается обозначением, соответствующим этому состоянию. Ориентированные дуги проводятся и обозначаются по следующему правилу. Пусть представляет собой множество значений для которых и пусть Если не пустое) множество, то дуга проводится из вершины в вершину , стрелка указывает направление из и обозначение дуги записывается в виде

Каждый, член вида содержащийся в обозначении дуги, называется парой вход - выход. Изложенное правило построения графа переходов автомата иллюстрируется рис. 2.1. Это правило устанавливает взаимно однозначное соответствие между графом переходов и таблицей переходов для одного и того же автомата, так что, зная одно представление, всегда можно получить другое. Для примера на рис. 2.2 изображен граф переходов автомата построенный по таблице 2.2.

Рис. 2.1. Обозначение дуги.

Рис. 2.2. Автомат

По построению графа дуга, направленная из вершины к вершине обозначается входными символами, которые вызывают переход автомата из состояния и выходными символами, которые выдаются автоматом при этом переходе. Для детерминированного, без ограничений на входе

автомата каждый входной сигнал вызывает переход из каждого состояния только в одно другое состояние; следовательно, дуги, выходящие из любой данной вершины, содержат полное число p пар вход - выход, где p — мощность входного алфавита. Непосредственное преимущество графа переходов состоит в том, что он облегчает определение реакции автомата на входную последовательность любой длины. При данном начальном состоянии автомата М и входной последовательности реакция М легко определяется прослеживанием (в направлении стрелок) непрерывной последовательности дуг, которая начинается в вершине дуга которой соответствует паре вход - выход Выходная последовательность, которую выдает автомат М при подаче на него входной последовательности тогда будет состояние, в которое при этом переходит М, определяется по обозначению вершины, в которой заканчивается последовательность из дуг. Например, реакция автомата на входную последовательность при начальном состоянии 3 легко определяется по рис. 2.2 и будет 0000001. Последовательность состояний при этом будет 1, 3, 4, 4, 4, 5 и 1.

Роль графа переходов в теории конечных автоматов подобна роли, которую играет графическое изображение схемы в теории электрических цепей. Граф переходов преобразует абстрактную модель в физическое изображение, усиливающее интуицию исследователя, и дает возможность ему «отчетливо представить» различные процессы и свойства, которые без такого изображения остались бы рядом сухих математических фактов. Как и в теории цепей, граф переходов удобно рассматривать как модель саму по себе, а символы, используемые в графе, — как абстрактные компоненты модели. Поэтому часто в дальнейшем мы будем граф, представляющий автомат М, называть «автоматом Ж», вершину, представляющую состояние — «состоянием и, наоборот, отождествлять абстрактные понятия с их геометрическими представлениями, имеющимися в графе переходов.

Понятие изоморфизма конечных автоматов, введенное в § 2.4, в терминах графов переходов допускает очень

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

8. Автоматы Мура, Мили и С-автоматы.

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

Автомат Мура может быть определён как кортеж из 6 элементов, включающий:

· множество внутренних состояний S (внутренний алфавит);

· начальное состояние S ₀;

· множество входных сигналов X (входной алфавит);

· множество выходных сигналов Y (выходной алфавит);

· функция переходов Φ (z, x).

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

Способы задания:

· Диаграмма — изображённый на плоскости ориентированный граф, вершины которого взаимно однозначно соответствуют состояниям автомата, а дуги — входным символам.

· Таблица переходов-выходов, в ячейках которой для каждой пары значений аргументов х(t), s(t) проставляются будущие внутренние состояния s(t+1). Значения выходных сигналов y(t) представляются в отдельном столбце.

Автомат Мили:

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

Автомат Мили — совокупность , где

· — конечное непустое множество состояний автомата;

· — конечное непустое множество входных символов;

· — конечное непустое множество выходных символов;

· — функция переходов, отображающая пары состояние/входной символ на соответствующее следующее состояние;

· — функция выходов, отображающая пары состояние/входной символ на соответствующий выходной символ;

· — начальное состояние.

Кодировка автомата Мили:

Вершина (операторная или логическая), стоящая после вершины " Начало", а также вход вершины " Конец" помечается символом S₁, вершины, стоящие после операторных помечаются символом S_n (n=2, 3..).

С-автомат:

под абстрактным С-автоматом понимают математическую модель

цифрового устройства, определяемую восьмикомпонентным вектором S = {A, Z, W, U,?,? 1,? 2, a1}, где А- множество состояний, Z- входной алфавит, W-выходной алфавит автомата Мили, U- выходной алфавит автомата Мура,? -функция переходов автомата,? 1- функция выходов автомата Мили,? 2- функция выходов автомата Мура, а1 – начальное состояние.

Автомат без памяти (КС): Алфавит состояний такого автомата содержит единственную букву, поэтому понятие функции переходов вырождается и становится ненужным для описания работы автомата, т.е. выходной сигнал в данном такте зависит только от входного сигнала того же такта и никак не зависит от ранее принятых сигналов.

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

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

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

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

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

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

Автомат, эквивалентный заданному и имеющий наименьшее из всех возможных число состояний называется минимальным.

Задача построения минимального автомата называется задачей минимизации автомата. Ее решение осуществляется в два этапа: сначала устанавливаются все неэквивалентные состояния исходного автомата, а затем по ним стоится минимальный автомат. В свою очередь, для определения неэквивалентных состояний необходимо выявить классы эквивалентных состояний.

Переход от А Мили к А Мура

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

S_A={A_A, Z_A, W_A, _A, _A, a_1A},

где

A_A = {а₁,:, а_m,:, a_M},
Z_A= {z₁,:, z_f,:, z_F},
W_A = {w₁,:, w_g,:, w_G};

_A - реализует отображение A_A х Z_A в A_A, _A - отображение A_A на W_A , а a_1A = a₁ - начальное состояние.
Построим автомат Мура

S_B={A_B, Z_B, W_B, _B, _B, a_1B},

у которого

Z_B= Z_A = {z₁,:, z_f,:, z_F},
W_B = W_A = {w₁,:, w_g,:, w_G};

Для определения А_B каждому состоянию a_s A_A поставим в соответствие множество A_s всевозможных пар вида (а_s, w _g), где w_g - выходной сигнал, приписанный входящей в а_s дуге (рис. 1-9): А_s={(a_s, w_g) | (a_m, z_f) = a_s и (a_m, z_f) = w_g}
Число элементов в множестве А_s равно числу различных выходных сигналов на дугах автомата S _A, входящих в состояние a_s.
Множество остояний автомата S_B получим как обединение множеств A_S (s=1,:, M):

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

Функции выходов _B и переходов _B определим слудиющим образом. Каждому состоянию автомата Мура S_B, представляющему собой пару вида (a_s, W_g), поставим в соответствие выходной сигнал W_g. Если в автомате Мили S_A был переход а1_B (а_m, z_f) = W_k , то в S_B (рис. 1-10) будет переход из множества состояний A_m, порождаемых a_m, в состояние (a_s, W_k) под действием входного сигнала z_f.
В качестве начального состояния а1_B можно взять любое из состояний множества А1, которое порождается начальным состоянием а1 автомата S_A. Напомним, что при сравнении реакции автоматов S_A и S_B на всевозможные входные слова не должен учитываться выходной сигнал в момент времени t=0, связанный с состоянием а1_B автомата S_B .

1.3.6. Пример преобразования автомата Мили в автомат Мура

Рассомотрим пример преобразования автомата Мили, изображенного на рис. 1-2, в автомат Мура. В автомате Мили Z_a={Z₁, Z₂}, W_a={W₁, W₂}, A_a= {A₁, A₂, A₃}, а1_A= а1, _A и _A определяются графом автомата. В эквивалентном автомате Мура

Z_B = Z_A = {Z₁, Z₂}, W_B = W_A = {W₁, W₂}.

1. Построим множество A_B, для чего найдем множество пар, порождаемых каждым состоянием автомата S_A:

A₁={(a₁, W₁), (a₁, W₂)} ={b₁, b ₂};
A₂={(a₂, W₁)}={b₃};
A₃={(a₃, W₁) (a₃, W₂)}={b₄ , b₅};
A_B=A₁U A₂U A₃={b₁, b₂, b ₃, b₄, b₅}.

2. C каждым состоянием, представляющем собой пару, отождествим выходной сигнал, являющийся вторым элементом этой пары:

_B(b₁) = _B (b₃) = _B(b₄) = W_1
B(b₂) = _B(b₅) = W₂

3. Рассматривая каждую пару и каждую связь, получим: так как в автомате S_A из состояния а1 есть переход под действием сигнала z₁ в состояние а₃ с выдачей сигнала W₁, то из множества A₁ = {b₁, b₂} порождаемых состоянием а1 в автомате Мура S_B должен быть переход в состояние {a₃, W₁}=b₄ под действием сигнала z₁.

Аналогично с состоянием A₁ должен быть переход в состояние {a₁, W₁} = b₁ под действием сигнала z₂ и так далее. В качестве начального состояния можно выбрать любую b₁, b₂ А₁. Если сагналы b_i заменить на а_i, то получим стандартное представление автомата Мура.

1.3.7. Пример перехода от автомата Мили с переходящим состоянием к автомату Мура

Рассмотрим переход от автомата Мили к автомату Мура, у которого входное состояние является переходящим. Будем составлять множество состояний следующим образом:

A₁U A₂U A₃={(a₂, W₁) (a₂, W₂) (a₃, W₁) (a₃, W₂)} = {b₂, b₃, b₄, b₅}.

К этим состояниям добавим пару (а₁, -) = b₁. Где " - " означает, что выходной сигнал в состоянии b₁ не определен. Функцию переходов S_B будем определять как и раньше.
Из данного графа получим граф:

В качестве начального состояния автомата Мура можно взять порождаемое им состояние.
Эквивалентность автоматов S_B и S_A при преобразовании автомата Мили в автомат Мура на множестве входных слов конечной длины легко доказать по индукции подобно изложенному выше при обратном преобразовании.

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

10. Абстрактный автомат. Соединение двух автоматов: параллельное