Абстрактная и структурная теории конечных автоматов. Структура операционного устройства. Способы задания автоматов, страница 19

- - 0 -,  -10-,   1 - 0 -, то переход к п.7, иначе переход к п.8.

7. Доопределить неопределенные значения r-го разряда четверкиa, b, g, d так, чтобы  значения этого разряда образовали набор 1100. Переход к п.9.

8. Дополнить коды состояний автомата одним неопределенным разрядом. Увеличить r на единицу. Переход к п.4.

9. Пара переходов (a_m,a_s), (a_k,a_l ) развязана. Конец.

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

Рассмотрим пример противогоночного кодирования. Закодируем состояния автомата, таблица переходов которого изображена на рис.3.5.

	a1	a2	a3	a4	a5
x1	a2	a2	a5	----	a5
x2	----	a1	a4	a4	----
x3	a1	a2	----	a1	a2

Рис.3.5.

Пары должны быть развязаны в каждом из массивов переходов M₁, M₂, M₃ , происходящих под действием сигналов x₁, x₂ , x₃.

M₁                                       M₂                                             M₃

(a₁ ,a₂)                                (a₂ ,a₁)                                       (a₁ ,a₁)

(a₂ ,a₂)                                (a₃ ,a₄)                                       (a₂ ,a₂)

(a_3,a₅)                                 (a₄,a₁)                                        (a₄,a₁)

(a₅,a₅)                                                                                   (a_5,a₂)

Развязывание пар переходов в М₁ начнём с первого перехода (а₁,а₂). Из-за совпадения состояния перехода пары типа (а₁,а₂), (а₂,а₂) развязывать не надо. Первая пара переходов, которая должна быть развязана, есть (а₁,а₂), (а₃,а₅).

Вводим переменную t₁  и образуем по этой переменной четвёрку (0011) для состояний а₁, а₂, а_3, а₅. Рассматриваемая пара переходов (а₁, а₂), (а₃, а₅), развязана (таблица 3.1).

Таблица 3.1.             t₁  

а₁     0

а₂       0

а₃     1

а₄      -

а₅       1

 

Пара переходов (а₁,а₂), (а₅,а₅) соответствует четвёрке (0011), то есть эта пара тоже развязана. Парам переходов (а₂,а₂), (а₃,а₅);  (а₂,а₂), (а₅,а₅) также соответствует четвёрка (0011), то есть они развязаны.

Далее переходим к рассмотрению пар из множеств М₂. В этом множестве подлежат развязыванию пары (а₂,а₁), (а₃,а₄) и (а₂,а₁), (а₄,а₄). Пара переходов (а₂,а₁), (а₃,а₄) образуют четвёрку (001-). Для развязывания доопределим четвёрку  до (0011), для чего состоянию а₄ поставим в соответствие t₁=1.

Таблица 3.2.            t₁  

а₁     0

а₂       0

а₃     1

а₄     1

а₅       1

 

Паре (а₂,а₁), (а_4,а₄) соответствует четвёрка (0011) (таблица 3.2).

Переходим к рассмотрению пар из множества М₃. Развязыванию подлежат пары: (а_1,а₁), (а₂,а₂);  (а₁,а₁), (а₅,а₂);  (а₂,а₂), (а₄,а₁);  (а₄,а₁), (а₅,а₂).

Из таблицы следует, что парам (а₁,а₁), (а₂,а₂) соответствует четвёрка (0000), то есть они развязаны. Вводим переменную t₂ и полагаем для а₁ значение t₂=0, а для а₂ значение t₂  равно 1 (таблица 3.3).

Для развязывания пар (а₁,а₁), (а₅,а₂), которым соответствует четвёрка