§ 9.9. Об ином определении эквивалентности последовательностных машин

Иногда в литературе встречается определение эквивалентности последовательностных машин, отличное от данного в § 9.4. Хотя это определение внешне похоже на наше, однако они сильно различаются по существу.

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

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

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

В определении, данном в § 9.4, требуется большее, чем в определении настоящего параграфа, а именно, чтобы соответствие состояний машины состояниям машины

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

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

Пример. Задан автомат А и множество L допустимых входных последовательностей, в котором содержатся все последовательности, не имеющие двух одинаковых символов подряд. Требуется построить минимальную Я-машину, отображающую относительно L автомат А, заданный основной таблицей (табл. . Диаграмма состояний автомата А изображена на рис. 9.23. Из табл. 9.4 в соответствии с § 9.7 следует, что при определении эквивалентности по § 9.4 минимальная П-машина, работающая как автомат А, будет иметь три состояния (так как никакие строки в табл. 9.4 не совпадают).

Таблица 9.4

Рис. 9.23.

Примем теперь указанное в этом параграфе определение эквивалентности и перестроим диаграмму состояний (рис. 9.23) автомата А, заменив ее диаграммой эквивалентной (в смысле § 9.4) машины, которая будет удобна для последующей минимизации. Перестройку произведем следующим образом. Заменим каждый кружок исходной диаграммы состояний кружками, обозначенными .

От каждого из новых кружков проведем те же стрелки с теми же надписями, которые отходили от исходного кружка.

Подходящие же к кружку стрелки распределим теперь следующим образом между новыми кружками: к кружку подходят лишь те из подходивших к кружку стрелок, которые имеют первый символ , к кружку

— имеющие первый символ и т. д.

Перестроив по этому правилу диаграмму состояний рис. 9.23, получим диаграмму состояний, показанную на рис. 9.24. В этом примере кольцевую стрелку с надписью , идущую от кружка к нему же, считаем и за отходящую и за подходящую; в качестве отходящей она заменяется стрелками, Отходящими от кружков на диаграмме рис. 9.24, которые подходят лишь к кружку . Кружок оказался охваченным кольцом.

Рис. 9.24.

Отметим, что из свойства диаграммы состояний рис. 9.23, состоящего в том, что к кружку подходят лишь ветви, имеющие надписи, вторые символы которых (это следствие того, что П-машина работает как автомат), следует свойство диаграммы состояний рис. 9.24: к любому кружку группы и т. д. подходят лишь стрелки со вторым символом .

На рис. 9.24 эти группы кружков обведены пунктирными линиями.

Перестроенная диаграмма состояний (рис. 9.24) соответствует машине эквивалентной (в смысле § 9.4) исходному автомату А (относительно множества Е всех возможных последовательностей). Чтобы убедиться, что диаграммы состояний рис. 9.23 и 9.24 есть диаграммы состояний эквивалентных машин, достаточно проверить, что состояния каждой группы, обведенной пунктирной линией на диаграмме рис. 9.24, эквивалентны между собой (образуют группу эквивалентных состояний). Заменив каждую группу эквивалентных состояний одним состоянием, мы возвращаемся к диаграмме рис. 9.23.

Итак, мы построили машину N, эквивалентную (в смысле § 9.4) автомату А и имеющую гораздо большее число состояний, чем автомат А ( состояний). Но эта диаграмма позволяет легко перейти от ограничений входных последовательностей «в себе» к ограничениям типа Ауфенкампа.

Рассмотрим какое-либо состояние, например состояние диаграммы рис. 9.24. Будем теперь подавать на вход машины N лишь последовательности из L (машина N эквивалентна в смысле § 9.4 автомату А и относительно L, так как ). Так как мы к состоянию можем подойти лишь по стрелке с надписью , т. е. путем подачи входного воздействия , отойти от него мы можем лишь по стрелке с надписью , потому что после нельзя подать еще раз . Следовательно, по стрелке , отходящей от кружка , мы никогда проходить не будем, и ее можно стереть. Исключение мог бы составить лишь начальный момент: если машине, находящейся в начальном состоянии было бы дано на вход воздействие , она перешла бы в состояние . Однако, принимая теперь новое определение эквивалентности машин (в смысле § 9.9), можно избежать этой неприятности, ибо вместо кружка в качестве начального можно выбрать кружок , от которого отходит стрелка с надписью к состоянию .

Рассуждая таким же образом, мы можем удалить из диаграммы состояний все стрелки, отмеченные тремя черточками.

В общем случае этот алгоритм «стирания стрелок» таков: стрелка с первым символом , отходящая от кружка (где — число штрихов), должна быть удалена. Перестроенная удалением стрелок диаграмма состояний рис. 9.24 изображена на рис. 9.25.

Рис. 9.25.

Полученная машина , диаграмма состояний которой изображена на рис. 9.25, работает так же, как машина N (и как автомат А), если на вход подавать лишь последовательности из L. Но машина эквивалентна относительно L машине (а следовательно, и автомату А) уже в новом смысле: соответствие состояний машин и N уже зависит от входной последовательности.

Машина имеет теперь ограничения типа Ауфенкампа: от каждого кружка отходят не все стрелки, т. е. от «ограничений в себе» мы перешли к машине с ограничениями типа Ауфенкампа.

Минимизируем теперь машину с помощью алгоритма, описанного в § 9.8. Матрица соединений машины имеет вид

Матрица в общем случае обладает свойством, вытекающим из отмеченных выше свойств диаграммы состояний: в столбце матрицы, соответствующем состоянию — число штрихов), могут стоять лишь пары .

Алгоритм предписывает для уменьшения числа состояний машины построить симметричное разбиение матрицы на обобщенные -матрицы.

В рассматриваемом случае достаточно разбить матрицу на обобщенные -матрицы только горизонтальными линиями; проведение вертикальных линий никогда не сможет «испортить» разбиения.

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

Заменяя каждую группу одним состоянием, возвращаемся к исходному автомату А (рис. 9.23) с тремя состояниями. Однако среди разбиений матрицы существуют и такие, для которых число групп минимально. В нашем случае одно из таких разбиений получаем, проведя линию между строками матрицы .

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

Проводя теперь симметричную вертикальную линию между столбцами и объединяя элементы каждой обобщенной -матрицы, получим матрицу соединений минимальной последовательностной машины

Ее диаграмма состояний изображена на рис. 9.26.

Рис. 9.26.

Машина осуществляет псевдоотображение машины . Но так как в этом случае множества допустимых входных последовательностей для всех состояний машины совпадают друг с другом и с L, то имеет место и отображение машины относительно множества .

Заметим, что матрица имела две пары совпадающих строк: . Первая строка ответствовала состоянию (рис. 9.25), а — состоянию . На диаграмме состояний (рис. 9.25) мы видим, что эти состояния могут быть только начальными — к кружкам, изображающим эти состояния, не подходят никакие стрелки. Эти состояния могут быть удалены с диаграммы состояний, так как состояние в качестве начального может быть заменено состоянием : от кружка как и от кружка , идет стрелка с надписью к кружку . Аналогично состояние в качестве начального может быть заменено состоянием .

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

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

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

Сравнивая теперь построенную машину диаграмма состояний которой изображена на рис. 9.26, с исходным автоматом А, диаграмма состояний которого изображена на рис. 9.23, мы убеждаемся, что действительно выбор соответствия состояний машин рис. 9.26 и рис. 9.23 зависит от входной последовательности.

Так, если машина рис. 9.23 начинает работать с состояния и получает входную последовательность , то для получения той же выходной последовательности машины рис. 9.26 ее следует установить в состояние если же машина рис. 9.23, находящаяся в том же состоянии , получает входную последовательность , то для получения той же выходной последовательности машину рис. 9.26 следует установить в начальное состояние .