Словесная формулировка условий работы автомата 2 страница

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

После заполнения выпишем группы совместимости.

Выписываем группы совместимых состояний:

1. 16, 17, 18

2. 7, 15, 19

3. 4, 5, 6, 14, 13

4. 7, 12, 15

5. 8, 9, 10, 11, 16

6. 3, 4, 5, 6, 13

7. 1, 2, 3, 4, 5, 6

8. 0, 7, 15

А	В	С	D	E	F	G	H
(16,17,18)	(7,15,19)	(4,5,6,14,13)	(7,12,15)	(8,9,10,11,16)	(3,4,5,6,13)	(1,2,3,4,5,6)	(0,7,15)

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

Таблица 7 – Таблица покрытия

F=H G G (F+G) (F+G+C) (F+G+C) (F+G+C) (B+D+H) E E E E D (C+F) C (B+D+H) (A+E) A A B=ABCDEGH

После всех упрощений выпишем минимальный класс совместимости: A, B, C, D, E, G, H

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

Словесная формулировка условий работы автомата 2 страница - student2.ru

Минимизированная таблица будет иметь вид:

У_В

У_Н

S₃

S₂

S₁

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

Словесная формулировка условий работы автомата 2 страница - student2.ru

Рисунок 10 – Граф перехода

Из графа видно, что:

1 При переходе из 2-го состояния в 0-е возникает критическое состязание т.к. меняется две переменных кодирования 0110-0000. Осуществим переход из 2-го в 0-е состояние через промежуточное 4-е состояние. Тогда смена кодов будет иметь вид 0110-0010-0000 что непротиворечиво.

2 При переходе из 5-го состояния в 0-е возникает критическое состязание т.к. меняется две переменных кодирования 0111-0000.Осуществим переход из 5-го в 0-е состояние через промежуточные 2 и 4-е состояния с кодом 0110 и 0010. Тогда смена кодов будет иметь вид 0111-0110-0010-0000 что непротиворечиво.

3 При переходе из 7-го состояния в 0-е возникает критическое состязание т.к. меняется две переменных кодирования 1001-0000. Осуществим переход из 7-го в 0-е состояние через 6-е состояние. Тогда смена кодов будет иметь вид 1001-0001-0000 что непротиворечиво.

4 При переходе из 3-го состояния в 4-е возникает критическое состязание т.к. меняется две переменных кодирования 1000-0010. Осуществим переход из 3-го в 4-е состояние через новое 8-е состояние с кодом 1010. Тогда смена кодов будет иметь вид 1 что непротиворечиво.

С учетом этого минимизированная таблица примет следующий вид: