Частично-определенные автоматы.

    Определение:

Частично-определeнный (неполностью-определeнный) автомат - это автомат, у которого функции "l" и/или "d" определены не полностью, значит, у него входные слова могут быть допустимыми и не допустимыми.

    Определение:

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

Свойства совместимости состояний:

     a_m ~ a_n,

     a_m ~ a_n => a_n ~ a_m,

     a_m ~ a_k & a_n ~ a_k !=> a_m ~ a_n ( т.е. нет транзитивности ).

    Утверждение: Два состояния a_m и a_n совместимы, то есть a_m ~ a_n если:

     d(a_m,z_i)=d(a_n,z_i) для любого z_i из Z, ( условие совместимости по переходу )

     l(a_m,z_i)=l(a_n,z_i) для любого z_i из Z . ( условие совместимости по выходу )

    Определение

Классом совместимости состояний C называют множество состояний, все элементы которого попарно совместимы друг с другом.

Класс совместимости максимален, если он не содержится полностью в другом. Классом совместимости также является класс B=d(C,z_i), если С - класс совместимости.

Начало формы

Алгоритм Ангера-Полла

Конец формы

Начало формы

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

                Нахождение всех максимальных классов совместимости.

                Нахождение минимального замкнутого покрытия.

                Получение по минимальному замкнутому покрытию нового автомата.

Конец формы

Первый этап.

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

d a1 a2 a3 a4 a5 z1 a2 a3 a3 -- -- z2 -- a5 a4 a1 -- z3 a3 a2 -- a2 a1 z4 a2 -- a5 -- --

l a1 a2 a3 a4 a5 z1 w1 w1 w1 -- -- z2 w2 w2 w2 w2 -- z3 -- w1 -- -- w2 z4 w1 -- w1 -- --

 

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

В треугольной таблице на пересечении строки m и столбца s ставятся:

              Х (крест), если состояния a_m и a_s несовместимы по выходу, например а₂ и а₅ (в таблице выходов в                      строке z₃ в столбцах a₂ и а₅ стоят разные выходные сигналы - w₁ и w₂ соответственно).

               множество всех пар состояний, следующих за парой (a_m, a_s) и отличных от неё - все те пары,                      совместимость которых необходима для совместимости пары (a_m, a_s). Например, для                      совместимости (а₁, а₃) необходима совместимость (а₂, а₃) и (а₂, а₅), так как (а₂, а₃) и (а₂, а₅)                      следуют за множеством (а₁, а₃) по входам z₁ и z₄ соответственно.

               V (птичка), если за (а_m, а_s) не следуют пары, отличные от (а_m, а_s), т.е. пара (а_m, а_s) совместима без                       дополнительных условий, налагаемых на совместимость других пар. В нашем примере это пара                      (а₃, а₅).

Для нахождения несовместимых пар состояний (и, следовательно, совместимых пар тоже) треугольная таблица просматривается по столбцам. Находится первая клетка, отмеченная крестом. Пусть это будет клетка   (i, j) - в нашем примере (2, 5). Тогда во всех клетках, где есть пара (i, j), ставится крест, а уже рассмотренная клетка (i, j) отмечается вторым крестом. Эта процедура проводится для всех клеток (включая новые), отмеченных одним крестом, и заканчивается, когда таких клеток не остается. Очевидно, что в этом случае клетки без крестов соответствуют совместимым парам состояний, а клетки с крестами - несовместимы. Так, после применения этой процедуры к треугольной таблице нашего примера, получаем следующий результат: "

a2 2.3 a3 2.3 2.5 4.5 a4 2.3 1.5 1.4 a5 1.3 X V 1.2 a1 a2 a3 a4

==>

a2 2.3 a3 2.3X 2.5X 4.5 a4 2.3 1.5XX 1.4 a5 1.3XX XX V 1.2 a1 a2 a3 a4

Из этой таблицы видно, что следующие пары состояний совместимы: (1, 2), (1, 4), (2, 3), (3, 4), (3, 5), (4, 5). А пары состояний (1, 3), (1, 5), (2, 4), (2, 5) не совместимы. Теперь рассмотрим способ нахождения максимальных классов совместимости из совместимых пар. Будем говорить, что множество состояний В   (В  А) совместимо с некоторым состоянием a_m  A (обозначение a_mВ), если и только если a_m a_s для любого a_s В.

Алгоритм нахождения всех максимальных классов совместимости сводится к следующему:

        Начинаем составление списка Ф классов совместимости с совместимых пар в крайнем правом столбце                треугольной таблицы, имеющем по крайней мере одну клетку без крестов. В примере Ф = {{4, 5}}.

        Продвигаясь влево, выписываем для каждого i-го столбца множество состояний А_i a_i, т.е. множество                всех состояний, соответсвующих клеткам без крестов в i-ом столбце таблицы. В нашем примере                3{4,5} (в третьем столбце таблицы нет крестов в строках 4 и 5).

              Каждое А_i пересекаем с каждым членом текущего списка Ф. У нас А₃ = {4, 5} и список Ф также                 содержит единственный элемент {4, 5}:

{4,5}{4,5}={4,5}.

             Если такое пересечение содержит более одного состояния, то добавляем в список объединение {a_i} с                результатом пересечения:

{3}{4,5}={3,4,5}; Ф={{4,5},{3,4,5}}.

             Далее проводится максимизация полученного множества Ф - устранение всех повторений множеств в                текущем списке и удаление всех множеств, содержащихся в других множествах списка:

Ф={{3,4,5}}.

             Добавляем в список все пары, состоящие из a_i и различных состояний из А_i, и не являющиеся                   подмножествами других членов списка Ф (при i = 3 таких добавлений нет).

             Приведём полностью результат применения второго шага ко всем столбцам:

Ф={{4,5}};

{3{4,5}, Ф={{3,4,5}};

{2{3}, Ф={{3,4,5},{2,3}};

{1{2,4}, Ф={{3,4,5},{2,3},{1,2},{1,4}};

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

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

Ф={{3,4,5},{2,3},{1,2},{1,4}}.

Второй этап - нахождение минимального замкнутого покрытия - достаточно сложная задача, не представляющая для нас особого интереса. Подробное описание этого алгоритма можно найти в книге С.И.Баранова "Синтез микропрограммных автоматов". Мы же в качестве исходного замкнутого покрытия возьмем множество максимальных классов совместимости Ф = {{1,2},{1,4},{2,3},{3,4,5}}.

Начало формы

Третий этап.

Процедура получения автомата S' = (A', Z', W', ', ', a₁'), представляемого найденным для исходного автомата S замкнутым покрытием D, достаточно проста. Каждому классу совместимости C_i D ставится в соответствие состояние a_i' нового автомата S'. Для каждого класса C_i D и каждого z_i Z вычисляем множество следующих за C_i состояний T_if = (C_i, Z_f).

Конец формы

Функции переходов и выходов определяются как

'(ai', zf) =	{	не определена, если Tif - пустое;
		aj', где aj' - состояние, соостветствующее одному из классов совместимости Ci D, включающему не пустое Tif
'(ai', zf) =	{	не определена, если Tif - пустое;
		aj', где aj' - состояние, соостветствующее одному из классов совместимости Ci D, включающему не пустое Tif

В качестве начального состояния a₁' автомата S' выбирается любое состояние из множества A', соответствующее некоторому классу совместимости, содержащему начальное состояние a₁автомата S.

Применим эту процедуру к нашему примеру. В качестве исходного замкнутого покрытия, как уже отмечалось выше, возьмем множество максимальных классов совместимости Ф = {{1,2},{1,4},{2,3},{3,4,5}} = {b₁, b₂, b₃, b₄}. Классу совместимости {1,2} ставим в соответствие состояние b₁ нового автомата. За классом {1,2} по входу z₁ следует класс {2,3}, по входу z₂ - класс {5}, по z₃ - класс {2,3}, по z₄ - {2}. Следовательно, чтобы автомат, получающийся в результате совмещения состояний {1,2} был детерминированным, должны быть совместимы состояния {1,2}, {2,3}, {5}, {2,3}, {2}, что в нашем случае верно. Таким образом получаем следующие значения функций переходов и выходов:

'(b₁, z₁) = b₃'(b₁, z₂) = b₄'(b₁, z₃) = b₃'(b₁, z₄) = b₃

'(b₁, z₁) = ₁'(b₁, z₂) = ₂'(b₁, z₃) = ₁'(b₁, z₄) = ₁

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

d b1 b2 b3 b4 z1 b3 b1 b3 b3 z2 b4 b1 b4 b2 z3 b3 b3 b1 b1 z4 b1 b1 b4 b4

l b1 b2 b3 b4 z1 w1 w1 w1 w1 z2 w2 w2 w2 w2 z3 w1 -- w1 w2 z4 w1 w1 w1 w1

 

Следует отметить, что в ряде случаев некоторые классы из множества максимальных совместимых классов для данного автомата не являются элементами минимального замкнутого покрытия, тогда как некоторые из их собственных подмножеств могут стать такими элементами. Кроме того, одни максимальные классы совместимости могут дать несколько элементов в минимальное замкнутое покрытие, а другие - ни одного. Число же минимальных замкнутых покрытий для некоторых частичных автоматов может значительно превышать число состояний этих автоматов. Поэтому практически более важной задачей является поиск одного минимального замкнутого покрытия для заданного автомата.

В частности, в нашем примере минимальным замкнутым покрытием является {{1,2},{2,3},{4,5}}. Соответствующий этому покрытию минимальный автомат имеет всего три состояния:

d {1,2} {2,3} {4,5} z1 {2,3} {2,3} -- z2 {4,5} {4,5} {1,2} z3 {2,3} {1,2} {1,2} z4 {1,2} {4,5} --

l {1,2} {2,3} {4,5} z1 w1 w1 -- z2 w2 w2 w2 z3 w1 w1 w2 z4 w1 w1 --

Композиция автоматов

    Рассмотрим основные виды соединений автоматов: параллельное, последовательное, с обратной связью, соединение с выходной функцией и соединение в сеть.

Параллельное соединение

    Параллельное соединение двух автоматов иллюстрируется на следующем рисунке:

Здесь S₁ = < Z₁, W₁, A₁, l₁, d₁ > и S₂ =< Z₂, W₂, A₂, l₂, d₂ >.

Результирующим автоматом параллельного соединения двух автоматов S₁ и S₂ назовем автомат S = < Z, W, A, l, d >, у которого:

     Z = Z₁ = Z₂,

     W = F(W₁,W₂ ),

     A = A₁ x A₂,

     l(ab,z) = f(l₁(a,z),l₂(b,z)),

     d(ab,z) = d₁(a,z),d₂(b,z).

Последовательное соединение

S₁=<Z₁,W₁,A₁,l₁,d₁>, S₂=<Z₂,W₂,A₂,l₂,d₂>

Результирующим автоматом последовательного соединения двух автоматов S₁ и S₂ назовем автомат S = <Z,W,A,l,d>, у которого:

     Z = Z₁

     W = W₂;

     W₁= Z₁;

     A = A₁ x A₂;

     l(ab,z) = l₂(b,l₁(a,z));

     d(ab,z) = d₁(a,z)d₂(l₁(a,z),b).

Соединение с обратной связью

Пример.

Соединение с выходной функцией

Пример.

Соединение в сеть

    Определение:

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

    Определение:

Сетью автоматов назовем шестерку N=<Z,W,{Si},{fi},{i},g> (i=1...n), где : Z - множество входов автомата-сети, W - множество выходов автомата-сети, S_i - компонентный автомат cети с алфавитом входов Z_i, образующийся из алфавита внутренних входов Z_i' и алфавита внешних входов Z_i'', с алфавитом выходов A_i, f_i : A₁ x...x A_n -> Z_i', _i : Z -> Z_i'', g : A₁ x...x A_n x Z -> W, n - количество компонентых автоматов.

Эквивалентная схема:

Пример.

1-я компонента:

1   z1 x1 z2 x1 z3 x2 z4 x3

d1 b1 b2 b3 x1 b1 b1 b3 x2 b3 b2 b3 x3 b3 b2 b1

2-я компонента:

2   z1 y1 z2 y2 z3 y1 z4 y2

f2 d1 d2 b1 q1 q2 b2 q1 q1 b3 q1 q1

d2 c1 c2 q1y1 c1 c1 q1y2 c2 c1 q2y1 c1 c2 q2y2 c2 c2

3-я компонента:

3   z1 t1 z2 t2 z3 t1 z4 t2

f3   c1 p1 c2 p2

d2 d1 d2 p1t1 d2 d1 p1t2 d1 d2 p2t1 d1 d2 p2t2 d1 d1

Выход:

q	d1	d2
c1	w1	w2
c2	w1	w1

Полученный автомат имеет 3 * 2 * 2 = 12 состояний.

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

    Под задачей композиции автоматов понимается задача нахождения для сети N ее результирующего автомата S_N.