§ 9.6. Минимизация последовательностной машины в случае, когда множество входных последовательностей не ограничено

Пусть задана последовательностная машина , имеющая k состояний. Разобьем все состояния машины S на группы эквивалентных состояний, например так, как это было описано в § 9.3. На рис. 9.5 изображена часть диаграммы состояний машины. Группы эквивалентных состояний обведены сплошными линиями. Рассмотрим подробнее какую-либо группу состояний, например первую группу. К состояниям первой группы подходят стрелки от других состояний машины, имеющие надписи и т. д. Отходящие стрелки, как это уже было установлено в § 9.3, могут быть двух типов:

а) Если какая-либо стрелка с первым символом , отходящая от одного из состояний группы, подходит к состоянию той же группы, то и все стрелки с первыми символами , отходящие от любого из состояний этой группы, подходят также к состояниям внутри группы. Вторые символы всех этих стрелок одинаковы.

б) Если стрелка с первым символом отходит от одного из состояний группы к одному из состояний группы, то и все стрелки с первыми символами , идущие от состояний группы, подходят только к состояниям группы. Вторые символы у всех этих стрелок совпадают.

Учитывая эти два свойства, заменим все состояния, входящие в одну и ту же группу, одним состоянием.

Все стрелки, подходящие к состояниям группы, подведем к кружку, заменяющему эту группу. Отходящие от состояний группы стрелки в случае а) заменим стрелкой-петлей с надписью , которая отходит от вновь введенного кружка, заменяющего группу состояний, и подходит к нему же, а в случае -одной стрелкой с надписью , идущей от кружка, заменившего все состояния группы, к любому кружку, заменившему состояния группы. На рис. 9.6 в качестве примера показана такая замена для части диаграммы состояний, приведенной ранее на рис. 9.5.

Рис. 9.5.

Рис. 9.6.

Произведем такую замену группы состояний одним состоянием для всех групп. После этого П-машина S преобразуется в П-машину G. Непосредственно видно, что П-машина G эквивалентна П-машине . Действительно, в силу свойств а) и б) при любой входной последовательности и любом начальном состоянии машина S выдает ту же самую выходную последовательность, что и машина G, если подвести к ней ту же входную последовательность и установить машину в начальное состояние , заменившее группу, в которую входило .

Вместе с тем число состояний в машине G равно числу групп эквивалентных состояний у S, и дальнейшее объединение состояний в группы невозможно,

В § 9.5 было показано, что число групп эквивалентных состояний одинаково во всех эквивалентных машинах, а в отображающих — не меньше. Минимальная машина не может иметь меньше состояний, чем число групп эквивалентных состояний минимизируемой машины. Поэтому машина G является минимальной для S. Отсюда следует, что при отсутствии ограничений на входные последовательности: 1. Минимальная машина находится в классе эквивалентных и 2. Задача минимизации сводится к обнаружению групп эквивалентных состояний, т. е. может быть решена алгоритмом Ауфенкампа и Хона (см. § 9.3).

В связи с этим удобно и замену групп состояний одним состоянием осуществлять не на диаграмме состояний, а непосредственно на матрице С.

В качестве примера вернемся к матрице С, рассмотренной ранее в § 9.3.

Осуществляя симметричное разбиение этой матрицы на -матрицы, получим

Состояния разбились на три группы эквивалентных состояний .

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

В рассматриваемом примере матрица соединений минимальной Я-машины G будет иметь вид

Ее диаграмма состояний показана на рис. 9.7.

Рис. 9.7.

Мы рассмотрели в этом параграфе случай, когда множество входных последовательностей неограничено. Задача о минимизации

П-машины при наличии ограничений «в себе» не решена в той же мере, в какой не решена для этого случая и задача о выявлении групп состояний, эквивалентных относительно L (см. § 9.4). Кроме того, минимизация относительно связана со следующей дополнительной трудностью. Пусть даже известен алгоритм выявления групп эквивалентных относительно L состояний. Выше в этом параграфе при мы могли заменять все состояния, входящие в каждую группу, одним состоянием. При этом мы опирались на свойства стрелок диаграммы состояний, описанных в пунктах а) и б). Если , то, вообще говоря, стрелки не обладают этими свойствами: от двух состояний, эквивалентных относительно L, стрелки с одинаковым первым индексом могут вести к неэквивалентным относительно L состояниям. Рассмотрим, например, кусок диаграммы состояний, показанной на рис. 9.8, в случае, когда L не содержит последовательностей, имеющих два одинаковых символа подряд. Пусть состояния эквивалентны относительно L, т. е. входят в одну группу.

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

Рис. 9.8.

Из изложенного следует, что при L Ф Е нельзя, вообще говоря, все состояния, входящие в каждую группу эквивалентных состояний, заменять одним состоянием, так как при этом пришлось бы от одного и того же нового состояния отвести две стрелки с одинаковым первым индексом к двум разным состояниям, что противоречит самому определению П-машины.

В этом параграфе мы не накладывали каких-либо ограничений на особенности переработки последовательностей минимизируемой П-машиной. В следующем параграфе будет особо рассмотрен частный случай П-машины, работающей как конечный автомат.