4. Минимизация состояний абстрактного автомата

Продолжим минимизацию автомата с помощью метода треугольных таблиц. По таблице 1.4 составим треугольную таблицу совместимости состояний (таблица 1.5). Отметим все совместные и несовместные состояния.

Таблица 1.5

Треугольная таблица совместимости состояний

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

v

x

x

x

x

x

x

x

x

v

x

x

v

v

x

v

x

x

x

x

x

x

x

x

x

x

v

x

x

x

v

x

v

x

x

x

x

x

x

x

x

x

x

v

x

x

x

v

x

x

x

v

x

x

x

x

x

x

x

x

v

x

x

v

v

x

x

x

x

x

v

x

x

x

x

x

x

x

x

v

x

x

v

v

x

x

x

x

v

x

v

x

x

x

x

x

x

x

x

v

x

x

v

v

x

x

x

x

v

v

v

x

x

x

x

x

x

x

x

x

x

v

x

x

x

v

x

x

v

x

x

x

v

x

x

x

x

x

x

x

x

x

x

v

x

x

x

v

x

v

x

x

x

x

x

x

v

x

x

x

x

x

x

x

x

v

x

x

v

v

x

x

x

x

v

v

v

x

x

v

x

x

x

x

x

x

x

x

x

x

v

x

x

x

v

x

v

x

x

x

x

x

v

x

v

x

x

x

x

x

x

x

x

x

x

v

x

x

x

v

x

x

v

x

x

x

v

x

x

x

x

v

x

x

x

x

x

x

x

x

v

x

x

v

v

x

v

x

x

x

x

x

x

x

x

x

x

x

v

x

x

x

x

x

x

x

x

v

x

x

v

v

x

x

x

x

v

v

v

x

x

v

x

x

x

v

x

x

x

x

x

x

x

x

x

x

v

x

x

x

v

x

x

v

x

x

x

v

x

x

x

v

x

x

v

x

x

x

x

x

x

x

x

x

x

v

x

x

x

v

x

v

x

x

x

x

x

v

x

v

x

x

x

x

x

v

x

x

x

x

x

x

x

x

v

x

x

v

v

x

v

x

x

x

x

x

x

x

x

x

x

v

x

x

x

c01

c0''

c1

c2

c3

c4

c5

c6

c7

c8

c9

c10

c11

c12

c13

c14

c15

c16

c17

c18

c19

c20

c21

c22

c23

c24

c25

c26

c27

c28

c29

Пары совместимых состояний:

c0' c16

c9 c15

c12 c15

c14 c16

c0" c15

c10 c16

c13 c15

c15 c26

c0' c17

c9 c18

c12 c18

c14 c17

c0" c18

c10 c17

c13 c18

c15 c30

c0' c21

c9 c19

c12 c19

c14 c21

c0" c19

c10 c21

c13 c19

c0' c22

c9 c20

c12 c20

c14 c22

c0" c20

c10 c22

c13 c20

c0' c24

c9 c23

c12 c23

c14 c24

c0" c23

c10 c24

c13 c23

c0' c25

c9 c26

c12 c26

c14 c25

c0" c26

c10 c25

c13 c26

c0' c28

c9 c27

c12 c27

c14 c28

c0" c27

c10 c28

c13 c27

c0' c29

c9 c30

c12 c30

c14 c29

c0" c30

c10 c29

c13 c30

c16 c22

c17 c21

c18 c19

c19 c20

c20 c23

c22 c24

c23 c27

c24 c29

c16 c24

c17 c25

c18 c20

c19 c23

c20 c27

c22 c29

c16 c29

c17 c28

c18 c23

c19 c27

c20 c25

c18 c27

c20 c28

c25 c28

c26 c30

Таблица 1.6

Пары состояний:

d	c
d0'	0' 16 22 24
d0"	0" 15 26 30
d1	1
d2	2
d3	3
d4	4
d5	5
d6	6
d7	7
d8	8
d9	9 19 20 23 27
d10	10
d11	11
d12	12
d13	13
d14	14
d15	17 21 25 28
d16	18
d17	26
d18	29

Таблица 1.7 Таблица переходов-выходов минимального автомата

y	d	0	1	d
0	d0'	d1	d2	d0'
1	d0"	d1	d2	d0"
b	d1	d3	d4
b	d2	d5	d6
b	d3	d7	d8
b	d3	d9	d10
b	d5	d11	d12
b	d6	d13	d14
b	d7	d0"	d0'
b	d8	d15	d16
b	d9	d9	d9	d0"
1	d10	d15	d0'
0	d11	d9	d9'
b	d12	d15	d17
1	d13	d9	d15
1	d14	d9	d0'
0	d15			d0"
0	d16			d0'
1	d17			d0"
1	d18			d0'

Проверим правильность минимизаций с помощью автоматной ленты.

0

0

0

0





1

0

0

0







d0’

d1

d3

d7

d0’

d0’

d0’

d0”

d2

d5

d10

d0’’

d0’’

d0’’

B

B

1

0

0

0

B

B

B

0

0

0

0

0

0

0

1





1

0

0

1







d0"

d1

d3

d7

d14

d0”

d0”

d1

d3

d5

d10

d0’

d0’

d0’

B

B

1

0

0

1

B

B

B

1

0

0

1

0

0

1

0





1

0

1

0





d1

d1

d3

d7

d14

d0”

d0”

d1

d3

d5

d11

d0’

d0’

d0’

B

B

0

1

0

0

B

B

1

1

1

1

0

0

1

1





1

0

1

1





d0’’

d1

d3

d7

d14

d0’’

d0"

d0’’

d0"

d2

d5

d10

d0’

d0’

d0”

B

B

0

0

0

0

B

B

1

1

0

0

0

1

0

0







1

1

0

0







d0’

d1

d4

d8

d15

d0’

d0’

d0’

d0’

d2

d6

d12

d14

d0"

d0"

d0"

B

B

B

1

1

0

0

B

B

B

1

0

1

0

0

1

0

1







1

1

0

1







d0’’

d1

d7

d13

d0’

d0’

d0’

d0’

d’’

d2

d6

d12

d0'

d0’

d0'

d0’

B

B

B

0

1

1

0

B

B

B

0

0

0

0

0

1

1

0







1

1

1

0







d0’

d1

d4

d9

d16

d0’’

d0’’

d0’’

d0’

d2

d6

d13

d0’

d0’

d0’

B

B

B

1

0

1

1

B

B

B

0

0

0

0

0

1

1

1







1

1

1

1







d0"

d1

d4

d9

d15

d0’

d0’

d0’

d0”

d2

d6

d13

d0’

d0’

d0’

B

B

B

0

1

0

1

B

B

B

1

1

1

1