 |
Этап минимизации автомата при абстрактном синтезе.
|
|
|
|
Минимизация полностью определенного автомата.
Постановка задачи:
Задан полностью определенный автомат A имеющий e – число состояний, необходимо построить эквивалентный ему автомат «A» c числом состояний «e1», причем e1 <= e.
Минимизация состоит в поиске эквивалентных состояний в автомате A и их объединений.
Два состояния S1 и S11 называются эквивалентными, если любую входную последовательность автомат перерабатывает в одинаковые выходные последовательности, в независимости от того какой из двух состояний S1 или S11 выбраны в качестве начального.(S1≡S11).
Отношение эквивалентности, определенное на множестве состояний обладает свойствами:
- Рефлексивность
S1≡S1
- Симметричность
S1≡S11 => S11≡S1
- Транзитивность
|
S1≡S111
S11≡S111
Отношение эквивалентности разбивает множество Ci на классы эквивалентности
S=C1ÚC2 ÚC3Ú…ÚCq
Ci <= S
Пересечение классов эквивалентности представляет собой пустое множество.
Пример:
Состояние Si ≡ Sk – не очевидно
Эквивалентный автомат будет:
Существует два необходимых условия эквивалентности состояний:
- Два состояния называются эквивалентными, если в этих состояниях вырабатываются одинаковые выходные символы (Мура) или при переходе из этих под воздействием любых одинаковых входных символов вырабатываются одинаковые выходные символы (Миля).
ψ1(S1) = ψ11(S11) (Мура)
ψ1(S1,Pk) = ψ11(S11,Pk) (Миля).
- Два состояния являются эквивалентными, если под воздействием любого одинакового входного символа переход осуществляется в эквивалентное состояние, т.е.
|
ψ1(S1,Pk) = Si
ψ11(S11,Pk) = Sj
Алгоритмы минимизации на основе треугольной матрицы.
|
|
|
Изначально нам задан автомат, имеющий L состояний.
- Строится треугольная матрица без диагональных элементов, столбцы которого нумеруются символами состояний с 1 по L-1, а строки со второй по L.
- Клетки матрицы с координатами i,j представляют отношение эквивалентностей между состояниями Si, Sj и заполняются следующим образом:
a) если для Si, Sj невыполнимо условие 1 эквивалентности, то в клетку ставят «X»
b) если выполняется заведомо два условия для Si, Sj (переходы осуществляются в одно и то же состояние для второго условия) – клетка оставляется пустой либо ставится «▼»
c) если для пары состояний Si, Sj выполняется 1 условие, но не известно выполняется ли второе, т.к. переходы осуществляется в разное состояние, то в клетку записывают номера состояний от эквивалентности которых зависит эквивалентность данных.
- Заполненная треугольная матрица, последовательно просматривающаяся по клеткам, в которых записаны состояния и если известно, что вписанная в клетку состояние не эквивалентны, то в этой клетки ставят «X».
Рассмотрение матрицы осуществляется до тех пор пока не перестанут появляться новые пары неэквивалентных состояний.
- Выписываются все пары эквивалентных состояний (там где не стоит X) и строят из них классы эквивалентностей. Каждому классу эквивалентности ставится в соответствие символ нового состояния и переписывают таблицу переходов входов и выходов путем объединения одинаковых строк.
Пример минимизации:
P = {a,b,c}
W = {1,2}
S = {1,2,3,4,5,6,7,8}
| Si / Pk | a | b | c |
| 1 | 4/1 | 2/2 | 5/1 |
| 2 | 5/2 | 1/1 | 4/2 |
| 3 | 3/2 | 5/1 | 4/2 |
| 4 | 5/1 | 8/2 | 4/2 |
| 5 | 7/1 | 2/2 | 1/1 |
| 6 | 1/1 | 3/2 | 4/2 |
| 7 | 5/1 | 3/2 | 7/2 |
| 8 | 3/2 | 5/1 | 6/2 |
Получили следующие пары эквивалентных состояний:
1 ≡ 5
3 ≡ 8
4 ≡ 6
4 ≡ 7
6 ≡ 7
Классы эквивалентности:
C1 = {1, 5}
C2 = {2}
C3 = {3, 8}
C4 = {4, 6, 7}
Получили 4 класса эквивалентности.
Далее перепишем:
|
|
|
C1 – 1
C2 – 2
C3 - 3
C4 – 4
Получим:
| Si / Pk | a | b | c |
| 1 | 4/1 | 2/2 | 5/1 |
| 2 | 1/2 | 1/1 | 4/2 |
| 3 | 3/2 | 1/1 | 4/2 |
| 4 | 1/1 | 3/2 | 4/2 |
| 1 | 4/1 | 2/2 | 1/1 |
| 4 | 1/1 | 3/2 | 4/2 |
| 4 | 1/1 | 3/2 | 4/2 |
| 3 | 3/2 | 1/1 | 4/2 |
Объединяем строчки: получим
| Si / Pk | a | b | c |
| 1 | 4/1 | 2/2 | 5/1 |
| 2 | 1/2 | 1/1 | 4/2 |
| 3 | 3/2 | 1/1 | 4/2 |
| 4 | 1/1 | 3/2 | 4/2 |
|
|
|
