Задачи синтеза относятся к классу комбинаторных. Их решение на основе полного перебора возможно лишь для задач малой размерности, не характерных для практических устройств. Поэтому используется сокращенный перебор, основанный или на эвристических действиях человека в диалоговом режиме работы с ЭВМ, или на применении приближенных алгоритмов решения комбинаторных задач.

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

Алгоритм определения подмножеств эквивалентных состояний включает следующие шаги:

1. Составляется квадратная матрица эквивалентных состояний порядка , где — число состояний автомата. Элемент матрицы = , если = или если для состояний и - существует хотя бы один входной сигнал, приводящий к разным значениям выхода; в противном случае = , где — множество пар состояний, в которые может перейти автомат из состояний и при одном и том же значении входа. При этом в множество включаются только такие пары и , в которых .

2. Если для какого-либо в имеется пара и , такая, что = , то принимается = .

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

Действие алгоритма иллюстрируется следующим примером.

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

() = ()/ (a) _

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

Кодирование внутренних состояний асинхронных автоматов чаще всего преследует цель устранить опасные состязания. Условие отсутствия опасных состязаний

(,) (,)= , (1)

где (,)—множество кодов состояний, которые могут появиться при переходе , т. е. в (,) входят коды состояний , и всех возможных промежуточных состояний. Например, (10011, 00111) = {10011, 00011, 10111, 00111}. Для выполнения (1) достаточно иметь в кодах для и хотя бы в одном разряде неодинаковые значения, не меняющиеся при переходах и . В частности, это условие выполняется, если разрешить при любом переходе изменение состояния только одного элемента памяти (одного разряда). Однако при таком способе кодирования требуется излишне большое число элементов памяти.

Чаще всего устойчивость автомата обеспечивается кодированием по методу разделения переходов. Алгоритм этого метода, называемый алгоритмом кодирования состояний по столбцам, заключается в поочередном рассмотрении столбцов матрицы переходов, за исключением лишь столбцов, в которых либо только одно, либо все состояния устойчивы. Под устойчивым состоянием понимается состояние, из которого при данном входном сигнале невозможны переходы в другие состояния. При рассмотрении -ro столбца его элементы разделяются на блоков по числу устойчивых состояний так, что в каждый блок входит одно устойчивое состояние и все стремящиеся к нему неустойчивые состояния. Предполагается, что автомат имеет одно и то же значение выхода для всех состояний, относящихся к одному и тому же блоку рассматриваемого столбца. Тогда для кодирования состояний, соответствующих блокам -то столбца, выделяется r_klog₂ двоичных разрядов. Для каждого блока выбирается свой r_k-разрядный код.

Для кодирования состояний без учета устойчивости требуется log₂ элементов памяти, где — число внутренних состояний. Обеспечение устойчивости требует увеличения : так, в примере получилось = 5 в сравнении с минимально возможным числом элементов, равным трем.