4.4. Минимизация памяти автомата

4.4.1. Построение треугольной таблицы

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

Таблица 8

Треугольная таблица

1

X

2

X

V

3

X

X

X

4

X

X

X

V

5

X

X

X

X

X

6

X

V

V

X

X

X

7

X

X

X

X

X

X

V

8

X

X

X

X

X

X

V

V

9

V

X

X

X

X

V

X

X

X

10

X

X

X

V

V

X

X

X

X

X

11

X

X

X

X

X

X

X

X

X

X

V

12

X

X

X

X

X

X

X

X

X

X

V

V

13

X

X

X

X

X

X

X

X

X

V

X

X

X

14

X

V

V

X

X

X

X

X

X

X

X

X

X

X

15

X

X

X

X

X

X

X

X

X

X

X

X

X

X

V

16

X

X

X

X

X

X

V

X

X

X

X

X

X

X

V

V

17

X

2, 18 V

Х

X

X

X

V

8, 18 V

X

X

X

X

X

X

V

16, 18 V

16, 18 V

18

X

2, 18 V

V

X

X

X

V

8, 18 V

V

X

X

X

X

X

V

16, 18 V

V

V

19

X

X

X

4, 20 V

4, 20 V

X

X

X

X

X

V

12, 20 V

12, 20 V

X

X

X

X

X

X

20

X

X

X

X

V

X

X

X

X

X

V

12, 20 V

V

X

X

X

X

X

X

V

21

X

X

X

X

X

X

X

X

X

X

V

X

X

X

X

X

X

X

X

20,22 V

20,22 V

22

X

X

X

X

X

X

X

X

X

X

V

X

X

X

X

X

X

X

X

20,22 V

V

V

23

X

X

X

X

X

X

X

X

X

V

X

X

X

X

X

X

X

X

X

X

X

X

X

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

где X — не совместимы;

V — совместимы;

2,18 — условно совместимы.