Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Этап минимизации автомата при абстрактном синтезе.




 

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

Постановка задачи:

Задан полностью определенный автомат A имеющий e – число состояний, необходимо построить эквивалентный ему автомат «A» c числом состояний «e1», причем e1 <= e.

Минимизация состоит в поиске эквивалентных состояний в автомате A и их объединений.

Два состояния S1 и S11 называются эквивалентными, если любую входную последовательность автомат перерабатывает в одинаковые выходные последовательности, в независимости от того какой из двух состояний S1 или S11 выбраны в качестве начального.(S1≡S11).

Отношение эквивалентности, определенное на множестве состояний обладает свойствами:

  1. Рефлексивность

      S1≡S1

  1. Симметричность

      S1≡S11 => S11≡S1

  1. Транзитивность

S1≡S11
      S1≡S111

           S11≡S111

Отношение эквивалентности разбивает множество Ci на классы эквивалентности

S=C1ÚC2 ÚC3Ú…ÚCq

Ci <= S

Пересечение классов эквивалентности представляет собой пустое множество.

Пример:

Состояние Si ≡ Sk – не очевидно

Эквивалентный автомат будет:

Существует два необходимых условия эквивалентности состояний:

  1. Два состояния называются эквивалентными, если в этих состояниях вырабатываются одинаковые выходные символы (Мура) или при переходе из этих под воздействием любых одинаковых входных символов вырабатываются одинаковые выходные символы (Миля).

ψ1(S1) = ψ11(S11) (Мура)

ψ1(S1,Pk) = ψ11(S11,Pk) (Миля).

  1. Два состояния являются эквивалентными, если под воздействием любого одинакового входного символа переход осуществляется в эквивалентное состояние, т.е.

Si≡Sj
ψ1(S1,Pk) = Si

ψ11(S11,Pk) = Sj

 

 

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

 

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

  1. Строится треугольная матрица без диагональных элементов, столбцы которого нумеруются символами состояний с 1 по L-1, а строки со второй по L.
  2. Клетки матрицы с координатами i,j представляют отношение эквивалентностей между состояниями Si, Sj и заполняются следующим образом:

a) если для Si, Sj невыполнимо условие 1 эквивалентности, то в клетку ставят «X»

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

c) если для пары состояний Si, Sj выполняется 1 условие, но не известно выполняется ли второе, т.к. переходы осуществляется в разное состояние, то в клетку записывают номера состояний от эквивалентности которых зависит эквивалентность данных.

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

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

  1. Выписываются все пары эквивалентных состояний (там где не стоит 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

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...