Главная  Кибернетика 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [ 72 ] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

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

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

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

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

Таблица 6.6

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

V- I

. 0



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.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [ 72 ] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

0.0009