Теория множеств. Тождества алгебры множеств. Основные понятия теории графов. Методы задания конечных автоматов. Синтез функциональной схемы конечного автомата, страница 36

1)  для каждого входного сигнала, для которого оба выхода определены, эти выходные сигналы совпадают: ;

2)  для каждого входного сигнала, для которого оба следующих состояния определены, переходы из  и  должны осуществляться в одно и тоже, либо в совместимые состояния: .

Пример. Для предыдущей таблицы  несовместимо с , т.к. , а  (несовместимость по выходу).

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

Определение. Множество состояний  () называется классом совместимости, если все состояния в  попарно совместимы.

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

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

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

1) Получают множество совместимых пар.

2) Находят максимальные классы совместимости.

3)  Находят минимальное замкнутое покрытие.

4)  Строят таблицу переходов – выходов минимального частичного автомата.

Этап 1. Нахождение множества совместимых пар состояний.

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

В пустые клетки этой таблицы для каждой пары ,  будем ставить

- символ , если  и  совместимы;

- символ , если   и  несовместимы;

- записывать множество всех пар состояний, совместимость которых               необходима для совместимости пары .

Проверяем возможность совместимости  пары состояний  .

Для этого рассматриваем столбцы состояний   и  в таблице переходов – выходов:

Видно, что состояния совместимы по выходам, но для совместимости этих состояний необходимо потребовать  совместимости состояний  и . Записываем это требование в пустую клетку треугольной таблицы, соответствующую паре . Для упрощения записей будем вписывать в клетку только номера состояний. В данном случае запись будет иметь вид 2,3

Аналогично проверяем остальные возможные пары состояний и заполняем соответствующие клетки.

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

Как видно из таблицы переходов – выходов пара   совместима без дополнительных условий, поэтому в клетку треугольной таблицы, соответствующей паре  ставим символ .

После заполнения таблица примет вид: