Алгоритм построения кратчайшего сохраняемого правильного покрытия
Начало. Задан частичный автомат . Требуется построить кратчайшее сохраняемое правильное покрытие.
Шаг 1. Строим все множества совместимости
и максимальное множество несовместимости.
Если максимальное множество несовместимости
построить трудно, то строим любое
множество несовместимости. Пусть
– мощность построенного множества
несовместимости.
Шаг 2. Из множеств совместимости
образуем последовательно покрытия
мощности
,
,
...,
и каждое из них проверяем на сохраняемость.
Первое в порядке получения сохраняемое
покрытие есть искомое кратчайшее
сохраняемое правильное покрытие.
Конец.
Объем перебора при работе данного
алгоритма довольно велик: он задается
величиной
,
где
– мощность списка множеств совместимости.
Пример. Рассмотрим частичный автомат , заданный таблицами переходов и выходов
|
|
|
|
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 |
Для него в подразделе 2.2.1 уже частично выполнен шаг 1 – найдены пары совместимых состояний. Список множеств совместимости имеет вид
Множество несовместимости, например,
имеет вид
.
Рассмотрим покрытие
.
Проверим покрытие на сохраняемость. Для этого сгруппируем в таблице переходов состояния по блокам. состояния, принадлежащие разным блокам, выделим разным шрифтом.
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
||
X\Q |
1 |
2 |
5 |
3 |
6 |
4 |
7 |
8 |
|
– |
5 |
1 |
2 |
1 |
6 |
– |
7 |
|
– |
– |
6 |
– |
– |
2 |
4 |
– |
|
– |
– |
– |
7 |
8 |
– |
3 |
1 |
|
4 |
– |
– |
4 |
– |
– |
4 |
4 |
Как видно из таблицы, покрытие не является
сохраняемым, поскольку по символу
состояния 7 и 8 переходят в разные блоки
покрытия.
Рассмотрим другое покрытие
.
Проверим его на сохраняемость.
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
5 |
1 |
3 |
6 |
4 |
7 |
8 |
|
– |
5 |
1 |
– |
2 |
1 |
6 |
– |
7 |
|
– |
– |
6 |
– |
– |
– |
2 |
4 |
– |
|
– |
– |
– |
– |
7 |
8 |
– |
3 |
1 |
|
4 |
– |
– |
4 |
4 |
– |
– |
4 |
4 |
Покрытие является сохраняемым. Построим по нему автомат, объединив столбцы матриц переходов и выходов для каждого блока покрытия, как показано в доказательстве достаточности теоремы.
|
|
y |
|
|
|
|
|
j |
|
|
X\Q |
|
|
|
|
|
X\Q |
|
|
|
|
|
|
|
|
|
|
a |
0 |
1 |
1 |
1 |
|
|
– |
|
|
|
b |
1 |
– |
1 |
0 |
|
– |
|
– |
|
|
c |
– |
0 |
– |
1 |
|
|
|
– |
|
|
d |
1 |
1 |
– |
0 |
Данный пример еще раз подтверждает, сколь велик перебор при построении кратчайшего сохраняемого правильного покрытия, поэтому на практике часто используются приближенные алгоритмы. Рассмотрим один из них.