logo search
Лекции по теории автоматов

Минимизация частичного автомата.

Она заключается в уменьшении числа состояний путем объединения совместимых состояний.

Алгоритм минимизации:

  1. Строится матрица и ищутся пары совместных состояний

  2. Находим maxклассы совместимости, например, с помощью дерева, которое разбивает искомый алфавит состояний на основе признака несовместимости пар состояний

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

  4. Проверяется полнота путем построения таблицы покрытий

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

  6. Каждому классу совместимости присваивается новый символ состояния.

  7. Переписывается таблица переходов, причем новое состояние записывается так, чтобы не нарушилась замкнутость и склеиваются совместимые строки.

Пример минимизации частичного автомата:

P= {a,b,c,d,e}

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

W = {00 , 01 , 10 , 11}

Si / Pk

a

b

c

d

e

1

1/00

5/*1

---

---

6/**

2

5/*0

4/0*

---

---

---

3

4/11

---

---

---

6/00

4

6/*1

6/00

---

2/0*

---

5

---

7/0*

---

4/*0

---

6

---

---

6/*0

---

2/10

7

---

2/**

1/00

---

---

Получили следующие пары совместимости:

1 ≡ 6

1 ≡ 7

2 ≡ 5

2 ≡ 6

3 ≡ 4

3 ≡ 5

3 ≡ 7

4 ≡ 6

4 ≡ 7

5 ≡ 6

Строим дерево классов:

C1= {1 , 6}

C2= {1 , 7}

C3= {2 , 5 , 6}

C4= {3 , 4 , 7}

C5= {3 , 5}

C6= {3 , 6}

Выбираем множество классов C1,C3,C4,C6

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