Алгоритмы минимизации на основе треугольной матрицы.

Изначально нам задан автомат, имеющий Lсостояний.

1. Строится треугольная матрица без диагональных элементов, столбцы которого нумеруются символами состояний с 1 по L-1, а строки со второй поL.

2. Клетки матрицы с координатами i,jпредставляют отношение эквивалентностей между состояниямиS_i,S_jи заполняются следующим образом:

1. если для S_i,S_jневыполнимо условие 1 эквивалентности, то в клетку ставят «X»

2. если выполняется заведомо два условия для S_i,S_j (переходы осуществляются в одно и то же состояние для второго условия) – клетка оставляется пустой либо ставится «▼»

3. если для пары состояний S_i,S_jвыполняется 1 условие, но не известно выполняется ли второе, т.к. переходы осуществляется в разное состояние, то в клетку записывают номера состояний от эквивалентности которых зависит эквивалентность данных.

3. Заполненная треугольная матрица, последовательно просматривающаяся по клеткам, в которых записаны состояния и если известно, что вписанная в клетку состояние не эквивалентны, то в этой клетки ставят «X».

Рассмотрение матрицы осуществляется до тех пор пока не перестанут появляться новые пары неэквивалентных состояний.

4. Выписываются все пары эквивалентных состояний (там где не стоит X) и строят из них классы эквивалентностей. Каждому классу эквивалентности ставится в соответствие символ нового состояния и переписывают таблицу переходов входов и выходов путем объединения одинаковых строк.

Пример минимизации:

P = {a,b,c}

W = {1,2}

S = {1,2,3,4,5,6,7,8}

Получили следующие пары эквивалентных состояний:

1 ≡ 5

3 ≡ 8

4 ≡ 6

4 ≡ 7

6 ≡ 7

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

C₁ = {1 , 5}

C₂= {2}

C₃= {3 , 8}

C₄= {4 , 6 , 7}

Получили 4 класса эквивалентности.

Далее перепишем:

C₁– 1

C₂– 2

C₃- 3

C₄– 4

Получим:

Объединяем строчки:получим