последовательность вход-выход в множестве Q{j (такие последовательности могут быть получены из таблицы для Q\ Q{f.....Q{f, построенной для определения ц по алгоритму 6.1). Тогда последовательность символов li С*,- Ъ,

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

р 2 Таким образом лг--таблица является табличным

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

Таблица 6.6

jc-г-таблица для Л28

6.5] МИНИМАЛЬНАЯ л;-г-ФУНКЦИЯ 225

чений {2ц-\-1) переменных (лг ц, z , x +l,,z .l, ...

х 1, z i, х), которые могут встретиться в данном автомате. Например, таблица 6.6 является АГ-2-таблицей автомата Л28, показанного на рис. 6.6.

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

Задача минимизации д:-2-функции на языке дг-г-таблицы может быть сформулирована следующим образом: вычеркнуть максимальное число столбцов из таблицы так, чтобы ни одна строка любой одной группы не стала одинаковой ни с какой строкой любой другой группы. Пусть столбцами, которые остались после такого вычеркивания, являются jfv /j. ATv-v Jfv-/„. z-j, z-j, .... Zv-y. Поскольку

v-\-u обязательно является минимальным числом аргументов и поскольку ни один упорядоченный набор значений u-\-v переменных не появляется в двух различных C-rpynnax АГ--таблицы, мы имеем:

Zv=f{Xv-l. JCv-Zj. .... -v-/. Zv-j, Zv-j, .... Tv-yJ,

(6.28)

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

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

Алгоритм 6.2. Задана АГ-2-таблица автомата М. Чтобы определить минимальную лг--функцию Л1 :(1) Полагаем Л = 1. (2) Для каждой комбинации из h столбцов проверяем, делает ли вычеркивание остающихся столбцов строки из различных Cft групп одинаковыми. (3) (а) Если каждая комбинация делает строки в различных Cft-rpynnax одинаковыми, то увеличиваем h на единицу и возвращаемся к (2). (б) Если есть комбинация, которая не делает строки в различных С-груп-пах одинаковыми, то берем эту комбинацию, соответствующую

столбцам ATv-jj, ЛГу-г •••• -1и -h -Уг.....•v-y„.

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

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

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

из Л столбцов. Проверка строк

Таблица 6.7

Минимальная дс-г-таблица для Л28

в этих трех столбцах показывает, что нет такой строки в 0-группе, которая была бы одинаковой с какой-либо строкой в 1-группе. Таким образом, для автомата Л28 можно записать:

2v = /(vv-i. v-2)- (6-29)

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

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