Алгоритм последовательных сокращений
Начало. Задан частичный автомат
.
Требуется построить кратчайшее
сохраняемое правильное покрытие. Положим
Шаг 1. Выберем очередную пару
1-совместимых состояний
.
Если такие пары исчерпаны, перейдем на
шаг 3. Иначе построим цепь
.
Если она неправильная, повторим шаг 1.
Шаг 2. Построим покрытие
по цепи
.
Пусть мощность покрытия
.
Если
,
положим
и запомним покрытие
.
Вернемся на шаг 1.
Шаг 3. Если
,
то по покрытию
построим автомат
и вернемся с ним на шаг 1.
Конец.
Пример. Пример. Рассмотрим частичный автомат из предыдущих примеров , заданный таблицами переходов и выходов
|
|
|
|
y |
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
– |
5 |
2 |
6 |
1 |
1 |
– |
7 |
|
– |
– |
– |
2 |
6 |
– |
4 |
– |
|
– |
– |
7 |
– |
– |
8 |
3 |
1 |
|
4 |
– |
4 |
– |
– |
– |
4 |
4 |
|
|
|
|
j |
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
– |
0 |
1 |
1 |
0 |
1 |
– |
1 |
|
– |
– |
– |
1 |
1 |
– |
0 |
– |
|
– |
– |
0 |
– |
– |
0 |
1 |
1 |
|
1 |
– |
1 |
– |
– |
– |
0 |
0 |
Построим все возможные цепи, порождаемые 1–совместимыми состояниями автомата. Выделим пары состояний в цепях, которые не являются 1-совместимыми.
;
;
;
;
;
;
;
;
;
;
;
;.
Неправильными здесь являются цепи
и
.
Любая из остальных цепей подойдет для
построения правильного сохраняемого
покрытия. Наименьшая мощность покрытия
получится, если взять, например, цепь
,
тогда покрытие, построенное по этой
цепи, имеет вид
Возможны и другие варианты выбора цепи.
Построим по этому покрытию новый автомат. Рассмотрим исходную таблицу переходов и выходов, сгруппировав столбцы в соответствии с блоками покрытия.
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
||
X\Q |
1 |
3 |
7 |
8 |
2 |
4 |
5 |
6 |
|
– |
2 |
– |
7 |
5 |
6 |
1 |
1 |
|
– |
– |
4 |
– |
– |
2 |
6 |
– |
|
– |
7 |
3 |
1 |
– |
– |
– |
8 |
|
4 |
4 |
4 |
4 |
– |
– |
– |
– |
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
||
X\Q |
1 |
3 |
7 |
8 |
2 |
4 |
5 |
6 |
|
– |
1 |
– |
1 |
0 |
1 |
0 |
1 |
|
– |
– |
0 |
– |
– |
1 |
1 |
– |
|
– |
0 |
1 |
1 |
– |
– |
– |
0 |
|
1 |
1 |
0 |
0 |
– |
– |
– |
– |
Таблицы переходов и выходов нового автомата имеют вид.
|
|
|
y |
|
|
|
X\Q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
– |
|
– |
|
|
– |
|
|
|
– |
– |
– |
|
|
|
|
– |
– |
– |
– |
|
|
|
j |
|
|
|
X\Q |
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
0 |
1 |
|
– |
0 |
– |
1 |
1 |
– |
|
0 |
1 |
– |
– |
– |
0 |
|
1 |
0 |
– |
– |
– |
– |
Строим для этого автомата все возможные цепи, порождаемые 1–совместимыми состояниями. При этом прекращаем построение цепи, как только в ней появилась не 1-совместимая пара, поскольку такая цепь является неправильной. В этом случае не 1-совместимую пару выделяем жирным шрифтом, а вместо пар, следующих за ней, пишем многоточие. Состояния для простоты записи будем обозначать цифрами без штрихов.
;
;
;
.
В новом автомате нет ни одной правильной цепи, значит, дальнейшая минимизация его невозможна. Пример подчеркивает приближенность метода – в предыдущем подразделе нам удалось сократить число состояний до четырех.