Определение несовместимых состояний

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

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

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

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

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

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

Рассмотрим алгоритм получения совместимых пар с помощью треугольной таблицы, предложенный М. Поллом и С. Ангером на примере не полностью определенного автомата, заданного таблицами переходов и выходов, приведёнными в табл.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.

По таблице выходов (см. табл. 2) определяются несовместимые по выходу состояния.

Несовместимыми по выходу состояниями являются состояния, у которых при воздействии на вход одного и того же слова x_i Î X, выходные слова имеют разные значения y_j Î Y.

При наличии таких состояний в треугольной матрице ставиться Х (крест).

Для определения таких состояний осуществляется последовательное сравнение состояний s₁ с s_2, s₁ с s₃, s₁ с s₄ и т. д.

Если при сравнении выходное слово не определено, то на основании допустимости входных слов, можно предположить, что выходные слова совпадают.

Сравним состояния s₁ с s₂ по таблице выходов (см.табл. 2).

x₁ => y₁ и y₁ - выходные слова совпадают;

x₂ => y₂ и y₂ - выходные слова совпадают;

x₃ => -/- и y₁ - выходные слова допустимо совпадают;

x₄ => y₁ и -/- - выходные слова допустимо совпадают.

На основании сравнения состояний можно сделать вывод о том, что состояния s₁ и s₂ совместимы по выходу.

Далее сравниваем состояния s₁ и s₃ по выше приведенной методике. Не трудно видеть, что состояния s₁ и s₃ совместимы по выходу.

При последовательном сравнении состояний по выходу обнаруживаем, что при сравнении состояний s₂ и s₅ выходные слова не совпадают.

x₁ => y₁ и -/- - выходные слова допустимо совпадают;

x₂ => y₂ и -/- - выходные слова допустимо совпадают;

x₃ => y₁ и y₂ - выходные слова не совпадают;

x₄ => -/- и -/- - выходные слова допустимо совпадают.

При наличии хотя бы одного несовпадения, состояния считаются несовместимыми. Следовательно, состояния s₂ и s₅ несовместимы и в ячейке треугольной матрицы на пересечении состояний s₂ и s₅ ставиться Х (крест).

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

Дальнейшие исследования совместимости состояний осуществляются по таблице переходов (см. табл. 1).

Дата добавления: 2015-07-02