12. Минимизация полностью определённых автоматов.

Рассмотрим метод, предположенный Ауфенкампом и Хоном.

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

Два состояния абстрактного автомата x_mиx_sназываются эквивалентными, если выходная функциядля всех возможных входных словФ. Иначе состояния называются неразличимыми.

Более слабой формой эквивалентности является k-эквивалентность:

для всех возможных слов длиной k.

Введённые отношения эквивалентности симметричны, транзитивны и рефлексивны. Следовательно, они могут быть использованы для разбиения множества состояний абстрактного автомата на попарно непересекающиеся классы – классы эквивалентности. Соответствующие разбиения на классы эквивалентности и k-эквивалентности будем обозначать через и. Разбиение позволяет определить избыточные элементы в множестве внутренних состояний. Если каждый класс эквивалентности содержит только одно состояние, то множество внутренних состояний не сократимо.

Рассмотрим алгоритм минимизации числа внутренних состояний полностью определённого автомата:

1. Находятся последовательные разбиения ,множестваXдо тех пор, пока на каком-то(k+1)шаге не окажется, что это разбиение ничем не отличается от предыдущего. Доказано, что в этом случае (=)есть необходимое нам разбиение, и дальнейшее сокращение числа внутренних состояний автомата невозможно.

2. В каждом классе эквивалентности разбиения выбирается по одному элементу, который образует множествоX’.

3. Функции переходови функция выходовдля автоматаопределяются на множестве оставшихся внутренних состояний и множестве входных сигналов. Для этого в таблице переходов вычеркиваются столбцы, соответствующие состояниям, не вошедшим в множество, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества. В таблице выходов столбцы вычёркиваются.

4. В качестве начального состояния выбирается одно из состояний, эквивалентныхX₀. На практике лучше взять самоX₀.

ПРИМЕР:

Минимизация полного автомата Мили:

Таблица переходов:

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X12

1

X10

X12

X5

X7

X3

X7

X3

X10

X7

X1

X5

X2

2

X5

X8

X6

X11

X9

X11

X6

X4

X6

X8

X9

X8

Таблица выходов:

	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12
1	1	1	2	2	1	2	1	1	2	2	2	2
2	2	2	1	1	2	1	2	2	1	1	1	1

={X₁,X₂,X₅,X₇,X₈} B₁,

{X₃,X₄,X₆,X₉,X₁₀,X₁₁,X₁₂ } B₂

X1

X2

X5

X7

X8

X3

X4

X6

X9

X10

X11

X12

1

B2

B2

B2

B2

B2

B1

B1

B1

B1

B1

B1

B1

2

B1

B1

B2

B2

B2

B2

B2

B2

B2

B1

B2

B1

={X1,X2} C₁,

{X5,X7,X8} C₂,

{X₃,X₄,X₆,X₉,X₁₁} C₃,

{X₁₀,X₁₂}C₄,

X1

X2

X5

X7

X8

X3

X4

X6

X9

X11

X10

X12

1

C4

C4

C3

C3

C4

C2

C2

C2

C2

C2

C1

C1

2

C2

C2

C3

C3

C3

C3

C3

C3

C3

C3

C2

C2

={X1,X2} D₁,

{X5,X7} D₂

{X8} D₃

{X3,X4,X6,X9,X11} D₄

{X10,X12} D₅

Соответственно, получили разбиение, для которого дальнейшее разбиение невозможно.

Произвольно выбираем из каждого класса по одному состоянию и формируем множество

	X1	X3	X5	X8	X10
1	X10	X5	X3	X10	X1
2	X5	X3	X3	X3	X8

	X1	X3	X5	X8	X10
1	1	2	1	1	2
2	2	1	2	2	1

Особенности минимизации для автомата Мура.

1

1

3

3

3

2

3

1

2

2

2

2

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X12

1

X10

X12

X5

X7

X3

X7

X3

X10

X7

X1

X5

X2

2

X5

X7

X6

X11

X9

X11

X6

X4

X6

X8

X9

X8

При минимизации автомата Мура вводится понятие 0-эквивалентностии, соответственно, разбиения множества внутренних состояний на 0- эквивалентные классы. 0- эквивалентными называются любые одинаково отмеченные состояния автомата Мура. Если два 0- эквивалентных состояния любыми входными сигналами переводятся в два 0- эквивалентных состояния, то они называются 1-экивавлентными состояниями.

={X1,X2,X8} А₁

{X3,X4,X5,X7} A₂

{X6,X9,X10,X11,X12} А₃