Абстрактный синтез конечного автомата

курсовая работа

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

По графу переходов построим таблицу переходов-выходов заданного автомата (таблица 3).

Таблица 3. Таблица переходов-выходов автомата

a(t-1)

0

1

a0

a1/1

a2/1

a1

a3/1

a4/1

a2

a10/0

a11/0

a3

-

a5/1

a4

-

a6/1

a5

a8/1

a9/0

a6

a8/0

-

a7

a0/-

a0/-

a8

a0/-

a0/-

a9

a0/-

a0/-

a10

-

a12/1

a11

a14/0

a15/0

a12

a13/1

-

a13

a0/-

a0/-

a14

-

a16/0

a15

a17/1

a18/0

a16

a0/-

a0/-

a17

a0/-

a0/-

a18

a0/-

a0/-

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

0 класс эквивалентности:

a0, a1

b0

a2, a11

b1

a14

b2

a3, a4, a10

b3

a5, a15

b4

a6

b5

a7, a8, a9, a13, a16, a17, a18

b6

a12

b7

1 класс эквивалентности:

a0

c0

a1

c1

a2

c2

a3

c3

a4

c4

a5, a15

c5

a6

c6

a10

c7

a11

c8

a12

c9

a14

c10

a7, a8, a9, a13, a16, a17, a18

c11

2 класс эквивалентности:

a0

d0

a1

d1

a2

d2

a3

d3

a4

d4

a5, a15

d5

a6

d6

a10

d7

a11

d8

a12

d9

a14

d10

a7, a8, a9, a13, a16, a17, a18

d11

Из разбиения видно, что классы 1 и 2 совпадают, значит, продолжать не имеет смысла.

Таблица переходов-выходов минимизированного автомата представлена в таблице 4:

Таблица 4. Таблица переходов-выходов минимизированного автомата

d(t-1)

0

1

d0

d1/1

d2/1

d1

d3/1

d4/1

d2

d7/0

d8/0

d3

-

d5/1

d4

-

d6/1

d5

d11/1

d11/0

d6

d11/0

-

d7

-

d9/1

d8

d10/0

d5/0

d9

d11/1

-

d10

-

d11/0

d11

d0/-

d0/-

Граф переходов минимизированного автомата представлен в приложении 2.

Делись добром ;)