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

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

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

Два состояния s_m и s_n совместимы, если для любого x_i  X, где функции определены, выполняются два условия:

• функции перехода совместимы ( s_m, x_i) ~ ( s_n, x_i) - условие совместимости по переходу. Это означает что при воздействии на вход автомата входного слова x_i, находящегося в состояниях s_m и s_n , он переходит в одно и тоже состояние s_к, либо в совместимые состояния.

• функции выхода равны ( s_m, x_i) = ( s_n, x_i) - условие совместимости по выходу. Это означает что при воздействии на вход автомата входного слова x_i, находящегося в состояниях s_m и s_n , на выходе будет одно и то же слово y_i.

Все совместимые состояния объединяются в классы совместимости.

Классом совместимости состояний C называют множество состояний, все элементы которого попарно совместимы друг с другом.

Например: состояния s_1, s_3, s₅ по приведенному признаку совместимы, следовательно они принадлежат одному классу совместимости С = {s_1, s_3, s₅}.

Классы совместимости могут пересекаться, то есть в различные классы могут входить одни и те же состояния цифрового автомата.

Класс совместимости максимален, если он не содержится полностью в другом классе.

Пример. Рассмотрим отношения классов совместимости С₁ = {s_1, s_3, s₅}, С₂ = {s_2, s_3, s₅, s_7, s_9,} и С₃ = {s_3, s_7, s₉}. Класс С₁ = {s_1, s_3, s₅} является максимальным по отношению к классу С₂ = {s_2, s_3, s₅, s_7, s₉} так как он полностью не содержится в классе С₂ (в классе С₂ отсутствует состояние s₁). В свою очередь класс С₂ по отношению к классу С₁ также является максимальным на основании выше приведенных условий (в С₁ отсутствуют состояния s_2, s_7, s₉). В тоже время класс совместимости С₃ = {s_3, s_7, s₉} не является по отношению к классу С₂ максимальным, так как полностью содержится в нём.

3. Определение совместимых состояний методом Ангера-Полла.

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

Далее процесс минимизации частичных автоматов включает в себя три основных этапа:

• нахождение всех максимальных классов совместимости;

• нахождение минимального замкнутого покрытия;

• получение по минимальному замкнутому покрытию минимизированного цифрового автомата.

Автомат называется минимальным, если в нём нет совместимых состояний.

Первый этап. Нахождение всех максимальных классов совместимости.

Рассмотрим алгоритм получения совместимых пар с помощью треугольной таблицы, предложенный М. Поллом и С. Ангером на примере не полностью определенного автомата, заданного таблицами переходов и выходов, приведёнными в табл.1 и 2.

По таблицам переходов и выходов автомата составляется треугольная таблица, столбцы и строки которой сопоставляются с состояниями автомата. Вид таблицы обусловлен рефлексивностью (s_m ~ s_n) и симметричностью (s_m ~ s_n => s_n ~ s_m) отношения совместимости состояний - она треугольная. Для упрощения записи в этой таблице вместо s_i будем писать i (символ состояния).

Порядок вычерчивания треугольной матрицы.

Количество строк матрицы m определяется из условия

m = I - 1, Таблица 4

где I - количество состояний автомата.

s2
s3
s4
s5
	s1	s2	s3	s4

При заполнении строк исключается первое состояние автомата s₁. Запись состояний осуществляется сверху вниз от s₂ до s_n (в нашем примере от s₂ до s₅).

Количество столбцов матрицы n определяется из условия

n = I - 1.

При заполнении столбцов матрицы исключается последнее состояние автомата s_n. Запись состояний осуществляется слева направо от s₁ до s_n-1 (в нашем примере от s₁ до s₄)_.

Треугольная таблица Ангера – Полла для рассматриваемого примера представлена таблицей 4.