Соединение автоматов. Параллельное соединение двух автоматов. Соединение двух автоматов с обратной связью, страница 5

Теперь легко заметить, что в новых таблицах переходов и выходов автомата S состояние a₅ соответствует состоянию a₄ автомата S^’. То есть реакции на последовательность Z у S и S^’ одинаковы. Значит автомат S^’ является минимизированным автоматом S.

Задача минимизации автомата S состоит в нахождении эквивалентного автомата S^’, содержащего минимальное возможное число состояний. Минимизация основывается на объединении в одно состояние множеств совместимых состояний.

Состояние  a₁, a₂, …, a_k называются совместимыми, если при подаче на вход автомата любого входного слова Z выходное слово W с точностью до неопределенных значений определяется только значением входного слова и не зависит от состояния a_i, в котором первоначально находился автомат. Множество совместимых между собой состояний автомата образуют класс.

Обеспечение устойчивой работы автомата.

При работе автомата может возникать эффект состязаний. Состязания возникают вследствие того, что элементы памяти имеют различные времена срабатывания. Кроме того, различны также задержки сигналов возбуждения, поступающих на входные каналы элементарных автоматов по логическим цепям. Если при переходе автомата из одного состояния в другое должны изменять свое значение несколько элементов памяти, то между ними начинаются состязания. Тот элемент, который «выигрывает» состязания, то есть раньше остальных изменит свое состояние, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементах до того, как другие участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в  непредусмотренное таблицей переходов состояние.