6.5. Минимальная x-z-функция

Если известна память конечного автомата М, то автомат может быть охарактеризован уравнением вида

Функцию соответствующую выражению (6.26), будем называть -функцией автомата М. Часто -функция содержит целый ряд несущественных переменных и может быть сведена к виду

где Функция называется минимальной x-z-функцией М, если -минимальное число аргументов необходимых для выражения z, как функции входных воздействий и выходных реакций в форме (6.27). Таким образом, минимальная -функция получается из -функции путем вычеркивания из последней максимально возможного числа аргументов Получение минимальной -функции, или минимизация -функции представляет интерес для целого ряда задач анализа и синтеза, когда для заданного конечного автомата желательна наиболее компактная форма его описания, т. е. форма (6.27).

Задача минимизации -функции может быть сформулирована более точно на языке -таблицы, общая форма которой показана в таблице 6.5.

Таблица 6.5. Общая форма -таблицы

Таблица разделена на q групп строк, по одной группе для каждого выходного символа в выходном алфавите автомата состояниями. Группу строк, обозначенную в столбце символом будем называть группой. Столбцы заполняются следующим образом. Пусть является парой вход - выход, связанной с дугой, которая начинается в состоянии и пусть

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

Таблица 6.6. -таблица для А28 (см. скан)

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

Из матрицы (6.23) видно, что пара вход - выход ) связана с дугой, которая начинается в состоянии 1. Из таблицы 6.4 видно, что множество состоит из последовательностей вход - выход (1/1) (1/0) и Следовательно, -группа в -таблице должна содержать строки 1,1,1,0,0 и 0,1,1,0,0. Остальные строки в таблице 6.6 заполняются аналогичным образом. Чтобы облегчить последующее изложение материала, придадим строкам и столбцам этой таблицы порядковые номера.

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

где — минимальная -функция.

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

Алгоритм 6.2. Задана -таблица автомата М. Чтобы определить минимальную -функцию М: (1) Полагаем

(2) Для каждой комбинации из h столбцов проверяем, делает ли вычеркивание остающихся столбцов строки из различных С групп одинаковыми. (3) (а) Если каждая комбинация делает строки в различных -группах одинаковыми, то увеличиваем h на единицу и возвращаемся к (2). (б) Если есть комбинация, которая не делает строки в различных -группах одинаковыми, то берем эту комбинацию, соответствующую

столбцам Минимальная -функция определяется выражением (6.28).

Выполнение алгоритма 6.2 становится значительно проще, если учесть следующие факты: (1) Каждая рассматриваемая комбинация из к столбцов должна включать либо столбец либо столбец (2) Если две строки, принадлежащие двум различным -группам, отличаются символами в единственном столбце, то этот столбец включается в каждую рассматриваемую комбинацию из Л столбцов. (3) Столбец, который содержит один и тот же символ в каждой строке, не должен включаться ни в какую рассматриваемую комбинацию из h столбцов. (4) Два одинаковых столбца вместе не должны включаться ни в какую рассматриваемую комбинацию из h столбцов.

Например, в таблице 6.6 можно заметить, что строки 3 и 18 различаются только значением переменной в столбце 2. Строки 1 и 16 различаются только значением переменной в столбце 4, строки 1 и 6 — только в столбце 5. Следовательно, при применении алгоритма 6.2 столбцы 2, 4 и 5 должны включаться в любую рассматриваемую комбинацию из h столбцов. Проверка строк в этих трех столбцах показывает, что нет такой строки в -группе, которая была бы одинаковой с какой-либо строкой в -группе. Таким образом, для автомата можно записать:

В этом выражении число аргументов минимально.

Таблица 6.7. Минимальная -таблица для

Минимальная -функция может быть представлена в табличной форме путем вычеркивания из -таблицы найденных по алгоритму 6.2 столбцов и объединения всех одинаковых строк. Получаемая в результате таблица называется минимальной лицей. Минимальная -таблица для автомата показана в таблице 6.7.