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

Два частичных автомата называются совместимыми, если

1. Они имеют одинаковый набор или множество допустимых входных слов.

2. Любое допустимое входное слово оба автомата перерабатывают в непротиворечие выходные слова, при условии что оба автомата находились в начальном состоянии.

Два выходных слова называется непротиворечивыми, если все символы, которые определены в выходном слове (первом) совпадает со всеми символами, которые определяются в выходном втором слове.

Пример:

Следовательно должны быть непротиворечивые выходные слова.

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

Отношение совместимости обладает следующими свойствами:

1. Рефлективностью S_i∞S_i– совместимо само с собой

2. Симметричностью S_i∞S_j S_j∞S_i

3. Нетранзитивно S_i¹∞S_i

S_i¹¹∞S_iно не следует, чтоS_i¹∞S_i¹¹

Отношение совместимости разбивает множество состояний на классы совместимости Q₁vQ₂ v…vQ_k, их объединение представляет собой алфавит состояний.Q_i ∩Q_j≠ 0 , т.е. пересечение двух классов совместимости не обязательно является пустым множеством, а следовательно одно и тоже состояние может оказаться нескольких классах совместимости. В общем случае число классов совместимости больше чем аналогичное число классов эквивалентности, но может и превышать число исходных состояний. Цель минимизации – уменьшить число состояний, а следовательно уменьшить число классов совместимости. Простым классом совместимости называют множество, содержащее попарно совместимые состояния. Максимальным классом совместимости называют простой класс, который не является подмножеством ни одного из наборов других классов. Условие совместимости состояний автомата:

1. Для любого входного символа функция выхода, если она определена для двух состояний должно совпадать (автомат Мили), либо для данных состояний должна совпадать (автомат Мура) ψ (S¹) = ψ (S¹¹) – Мура, ψ (S¹,P_k) = ψ (S¹¹,P_k) – Мили

2. Для любого входного символа P_k, если функция перехода для двух состояний определена, то переход осуществляется в одно и то же состояние, либо в совместимое.

во втором случае в отличие от первого S¹не совместимо сS¹¹

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

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

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

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

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

C₁= {1 , 6}

C₂= {1 , 7}

C₃= {2 , 5 , 6}

C₄= {3 , 4 , 7}

C₅= {3 , 5}

C₆= {3 , 6}

Выбираем множество классов C₁,C₃,C₄,C₆

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