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

(00 -1), для а₅ полагаем значение t₂ =1 (таблица 3.4).

Для развязывания пар (а₂, а₂), (а₄,а₁), которым соответствует четвёрка (11 -0), для а₄ полагаем значение t₂ = 0 (таблица 3.5).

Из таблицы 3.5 следует, что пары (а_4,а₁) ,(а₅,а₂) развязаны.

Таблица 3.3.                                                      Таблица 3.4.

Развязывание пар (а₁,а₁), (а₂,а₂)                     Развязывание пар (а₁,а₁), (а₅,а₂)

t₁       t₂                                                          t₁       t₂               

         а₁   0      0                                                    а     0     0

         а₂   0      1                                                    а₂    0     1

         а₃   1      -                                                    а₃     1     -

         а₄    1      -                                                    а₄     1     -

         а₅   1      -                                                    а₅     1     1

                                          Таблица 3.5.                                                         

Развязывание пар (а₂,а₂), (а₄,а₁)                    

t₁       t₂                                                            

                                                 а₁    0     0                                                      

                                                 а₂    0     1

                                                 а₃     1     -                             

                                                 а₄     1    0                                                       

                                                 а₅     1    1    

 

В рассматриваемом автомате 5 состояний. Минимальная длина слова для кодирования пяти состояний равна ]log₂5[=3. Поэтому вводим переменную t₃ и произвольным образом придаём ей значения для состояний а₁, а₂, а₃, а₄, а₅ таким образом, чтобы эти состояния были отмечены различными кодами.

Аналогичным способом присваиваем значение t₂  для а₃ .

Окончательный результат кодирования приведён в таблице 3.6.

                 Таблица 3.6.            t₁      t₂     t₃

а₁       0      0      0

                                      а₂     0      1      0

                                      а₃     1      0      0

                                      а₄     1      0      1

                                      а₅     1      1      0

Переменные t₁, t₂, t₃ соответствуют состояниям триггеров автомата.

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

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

1. Заменить в абстрактных таблицах переходов и выходов входные и выходные абстрактные сигналы на структурные.

2. Заменить абстрактные состояния (а₁,а₂,…,а_n) на структурные, выраженные в соответствии с полученными кодами через состояния триггеров. Например, если произвольное состояние кодируется 01011, то  в таблицах переходов  и выходов записывается вместо а_I :   ₁ t_{2 3} t₄ t₅ .

3. Для каждого триггера T_i (i = 1,2,…,m, где m-общее количество триггеров в автоматеавтомата записать функции возбуждения  по единичному входу (переводит триггер в состояние 1) и по нулевому входу (переводит триггер в состояние 0).  равна дизъюнкции всех существующих логических произведений, каждое из которых состоит из двух сомножителей: состояния и входного сигнала, образованных по следующему правилу:

Если в состоянии, обозначающем какой-либо столбец, например r, таблицы переходов t_i входит в инверсном виде (_i ), а в состоянии, находящемся на пересечении с j строкой, обозначенной входным сигналом  x_i, входит в прямом виде ( t_i ), то в качестве сомножителей логического произведения берется состояние, обозначающее столбец, и входной сигнал, обозначающий jстроку.