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

[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]

Процесс отыскания минимальной формы автомата называется минимизацией автомата. Минимизация автомата М состоит в определении эквивалентного разбиения Жив последующем применении (3.15) для построения Ж. Так как при применении (3.15) все состояния Ж, принадлежащие одному и тому же классу эквивалентности, дают один и тот же результат, то индивидуальное распознавание каждого состояния становится ненужным; для целей минимизации важно распознавание класса, к которому принадлежит каждое состояние. Поэтому всем состояниям Ж, принадлежащим классу эквивалентности 2;, можно приписать общее обозначение, например, а[. После этого (3.15) может быть интерпретировано как формулировка того, что автомат Ж получается из автомата Ж путем «объединения» одинаково обозначенных состояний в одно состояние. Способы, которыми это объединение производится, существенно зависят от того, каким образом определен автомат - таблицей, графом или матрицей. Эти способы будут описаны ниже. Хотя понимание этих способов облегчается благодаря предшествующей интуитивной интерпретации условия (3.15), их справедливость не зависит от этой интерпретации и вытекает непосредственно из самого условия.

Таблица переходов Ж. Если заданы таблица переходов и эквивалентное разбиение 2j, 2.....2- автомата Ж, то

таблица переходов автомата Ж может быть построена следующим образом: (1) заменим обозначение каждого состояния, которое имеется в таблице переходов Ж, на обозначение класса, которому данное состояние принадлежит; (2) из каждой группы строк с одинаковыми обозначениями в клетках основного столбца (все такие строки являются одинаковыми в обеих подтаблицах 2 и s+i) вычеркнем все строки, кроме одной. Полученная при этом таблица является таблицей переходов Ж.

Например, автомат Л7, представленный таблицей 3.2, имеет классы эквивалентности {1, 3, 8}, {2, 4}, {5, 7}, {6} и {9}. Обозначим их произвольно 1, 2, 3, 4 и 5 соответственно. Делая первый шаг процедуры, заменим каждое обозначение «1», «3», и «8» в основном столбце и в s+j подтаблице таблицы 3.2 на «1», каждое «2» и «4>-на «2»,



«5» и «7» - на «3», «6» - на «4», «9» - на «5». Полученная в результате таблица переходов приведена в таблице 3.14. Вычеркивание всех повторяющихся строк дает таблицу переходов А7, показанную в таблице 3.15-

Таблица 3.14

Шаг 1 при построении таблицы переходов для автомата А7

S \

S \

Таблица 3.15

Автомат А1

S \

S \

Граф переходов М. Если заданы граф переходов и эквивалентное разбиение 2j, S- 2- автомата М, то

граф переходов автомата М может быть построен следующим образом: (1) заменим обозначение каждого состояния, которое имеется в графе переходов М, на обозначение класса, к которому относится данное состояние; (2) объединим все одинаково обозначенные состояния (рассматривая дуги графа как «гибкие связи») и представим объединенные состояния одним состоянием, имеющим общее обозначение; (3) из ка-



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

В качестве примера на рис. 3.9 приведен граф переходов автомата А1, полученный в результате применения опи-


Рис. 3.9. Автомат А7.

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

Матрица переходов М. \ Если заданы матрица перехо- дов и классы эквивалентности

2j, .....автомата М,

то матрица переходов автомата М может быть построена следующим образом: (1) произведем симметрическую перестановку и симметрическое разбиение [уИ], так чтобы строки (и столбцы) группировались соответственно классам эквивалентности М (в результате получим матрицу такую же, как окончательная матрица [Ж]**, получаемая при матричном методе эквивалентного разбиения); (2) заменим все обозначения строк (и столбцов) каждой группы, представляющей класс эквивалентности, одним обозначением этого класса; (3) заменим каждую подматрицу в разбитой матрице одной клеткой, содержащей все пары вход-выход, которые имеются в любой строке этой подматрицы (все строки в любой такой подматрице содержат одно и то же множество пар вход-выход). Полученная в результате матрица будет матрицей переходов Ж.

В качестве примера приведена матрица (3.16), представляющая собой матрицу переходов А7, построенную по показанной в (3.14) матрице [Л7](»>. Использованные здесь обозначения классов эквивалентности Л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.001