Абстрактная и структурная теории конечных автоматов. Структура операционного устройства. Способы задания автоматов, страница 6

Рис.1.4   Частично определенный автомат

Полнота системы переходов автомата в общем случае означает, что для любой пары состояний автомата (a_m,a_s) существует входной сигнал z_f ,  так что определена функция a_s=d(a_m,z_f). Автомат обладает полной системой выходов, если каждому его состоянию соответствует выходной сигнал w_g, отличный от выходных сигналов других состояний.

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

Выделяют два этапа синтеза конечных автоматов: абстрактный и структурный. Целью структурного синтеза является построение схемы реализующей автомат из логических элементов и элементов памяти заданного типа или же его программная реализация. Целью абстрактного синтеза автомата, при котором отвлекаются от структуры как самого автомата, так и его входных и выходных сигналов, является получение минимальных таблиц переходов и выходов на основе отмеченного графа алгоритма или диаграмм состояний и переходов.

1.3.  Минимизация абстрактных таблиц переходов и выходов автомата

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

Состояния а₁,а₂,...а_к называются совместимыми, если при подаче на вход автомата любого входного слова z_i = z_i1z_i2...z_in выходное слово w_iс точностью до неопределённых значений определяется только значением входного слова и не зависит от состояния a_iÎ{a₁,a₂,...,a_k}, в котором первоначально находился автомат. Если в вышеприведённом определении длину входного слова ограничить l символами, то состояния, удовлетворяющие этому определению, будут называться  l- совместимыми. В частности, если состояния а₁,а₂,...а_к одно-совместимые, то при подаче на вход автомата одного любого входного сигнала z на выходе автомата будет сигнал, определяемый только значением входного сигнала, а не состоянием а_iÎ{a₁,a₂,...a_k}, в котором находился первоначально автомат.

Одно-совместимые состояния могут быть просто найдены по таблице выходов автомата Мили. Если некоторые столбцы таблицы выходов одинаковые, с точностью до неопределённых сигналов, то состояния, отмечающие эти столбцы, одно-совместимые. На рис.1.5 приведена таблица выходов автомата.

Рис.1.5   Таблица выходов

В приведённом автомате имеется два множества  одно-совместимых состояний:  1) {a₁,a₂}   2) {a₃,a₄} .

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

Алгоритм минимизации числа состояний автомата S следующий:

1) Находятся последовательные разбиения p₁,p₂,...p_к,p_к+1 множеств состояний автомата A={a₀,a₁,a₂,...a_M} на классы одно-, двух-, k-, (k+1)-совместимых состояний до тех пор, пока на каком-то k+1 шаге не окажется, что p_к+1=p_к. Разбиение p_к называется предельным.

2) В каждом предельном классе k - совместимых состояний выбирается по одному состоянию, которые образуют множество состояний минимального автомата , эквивалентного автомату S.