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

К проблеме минимизации в этом случае естественно подойти следующим образом.

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

а) Всякая входная последовательность, допустимая для машины N, находящейся в состоянии , была бы допустима и для машины , находящейся в состоянии

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

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

Таким образом, машина , осуществляющая псевдоотображение машины N, «может делать» все то, что и машина . Она может воспринять любую входную последовательность, допустимую для машины N, и переработать ее в ту же самую выходную последовательность.

Ниже описан алгоритм Ауфенкампа, позволяющий строить машину , осуществляющую псевдоотображение машины N с меньшим числом состояний, чем машина , но не обязательно минимальную.

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

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

Рассмотрим, например, матрицу соединений

В первой строке этой матрицы нет пары, связанной с воздействием , во второй строке — с а в четвертой строке есть всего одна пара, связанная с .

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

В [5] доказывается теорема, которую мы здесь при водим без доказательства: если матрица С симметрично разбита на обобщенные 1-матрицы, причем в каждой строке обобщенных 1-матриц не встречаются две матрицы, в которых есть пары, имеющие одинаковые первые символы, то состояния в каждой группе разбиения псевдоэквивалентны.

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

Построение симметричного разбиения проиллюстрируем на примере. Пусть машина N имеет диаграмму состояний, показанную на рис. 9.13. Ее матрица соединений С была приведена на стр. 341. Разобьем сперва матрицу С горизонтальными линиями на обобщенные 1-матрицы. В отличие от случая, когда машина не имела ограничений и разбиение на 1-матрицы производилось единственным способом (с точностью до порядка строк внутри группы), здесь возможно несколько вариантов. Так, можно разбить строки на три группы, включив в первую группу строки (так как они образуют обобщенную -матрицу), во вторую группу — строки и в третью группу — строку. Можно разбить строки и по-иному, на две группы, включив в первую группу строки, а во вторую — строки.

Рис. 9.13.

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

Выберем, например, такой вариант разбиения строк матрицы С на две группы: в первую группу войдут строки, а во вторую — . Проводим горизонтальную линию между строками матрицы С и разбиваем ее на две обобщенные 1-матрицы.

Теперь следует симметрично провести вертикальную линию между столбцами. Эта линия наше разбиение «портит», так как в нижней строке подматриц оказались две обобщенные 1-матрицы, содержащие пары с одинаковыми первыми символами . Чтобы исправить положение, проведем горизонтальную линию между строками (в общем случае имеется также несколько вариантов «исправления»). Теперь уже нет строк подматриц, содержащих пары с одинаковыми первыми символами.

Проводим еще симметричную вертикальную линию между столбцами, на чем симметричное разбиение и заканчиваем.

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

Ее диаграмма состояний приведена на рис. 9.14.

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

Рис. 9.14.

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

Машина , осуществляющая псевдоотображение машины N, имела бы уже четыре состояния и матрицу

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

Кроме того, этот алгоритм не обязательно дает минимальную машину Р. Известны примеры, когда машина N имеет группы псевдоэквивалентных состояний, которые могут быть заменены одним состоянием (тем самым машина N минимизируется), а условие теоремы, приведенной в этом параграфе, не выполняется.

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

Рис. 9.15.

Матрица соединений П-машины рис. 9.15 имеет вид

Матрица С может быть только двумя способами симметрично разбита на обобщенные 1-матрицы, так что состояния разбиваются на группы первым способом и вторым способом:

Легко убедиться, что как в первом, так и во втором случае условия последней теоремы Ауфенкампа (см. стр. 342) не выполняются: в первом случае две верхние обобщенные 1-матрицы разбиения имеют общую пару , связанную с входным воздействием во втором случае общими оказываются пары . В то же время исследуемая машина, (рис. 9.15) имеет минимальную П-машину с двумя состояниями, диаграмма состояний которой изображена на рис. 9.16. Соответствие состояний при псевдоотображении таково: состояниям соответствует состояние , а состоянию — состояние .

Ниже описан метод Гилла, позволяющий строить минимальную машину для любой заданной П-машины с ограничениями типа Ауфенкампа (см. [149]). При применении этого метода следует прежде всего выписать все пары совместимых состояний заданной машины. Для определения совместимости состояний известно много различных приемов. Опишем один из них.

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

Если при этом хотя бы при одном входном воздействии получаются разные выходы, несовместимость состояний уже выявлена. В противном случае на ветвях надписываются соответствующие пары «вход — выход», а в конце ветвей указываются те состояния, в которые переходят состояния .

Далее процесс повторяется, исходя из вновь построенных узлов. В ходе построения узлов вновь возникающие узлы вычеркивают в следующих трех случаях:

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

2. Если обе надписи у узла совпадают, т. е. выходя из состояний на этом шаге подходим к одному и тому же состоянию.

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

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

Рис. 9.16.

В качестве примера на рис. 9.17 показано такое дерево для определения совместимости состояний машины рис. 9.15, а для определения совместимости состояний машины рис. 9.18 дерево имеет вид рис. 9.19.

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

Рис. 9.17.

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

Имея возможность распознавать совместимость состояний, можно для всякой машины выписать все пары совместимых состояний. Для машины рис. 9.15 таких пар две: , а для машины рис. 9.18 — девять пар:

Далее следует построить группы псевдоэквивалентных состояний. Например, в списке (9.3) содержатся пары состояния образуют группу псевдоэквивалентных состояний .

Рис. 9.18.

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

В общем случае, как и в данном примере, эти группы пересекаются.

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

Рис. 9.19.

Обозначим множество всех состояний машины S, соответствующих состоянию машины через и предположим, что построены такие множества состояний мащины для всех состояний машины . Это разбиение состояний машины S обладает следующими свойствами:

1. Разбиение охватывает все состояния машины S, т. е. для всякого состояния машины S можно указать одно или несколько множеств 2, которым это состояние принадлежит.

2. Состояния, принадлежащие любому , псевдоэквивалентны.

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

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

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

Разбиение называется собственным разбиением состояний машины .

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

Таким образом, этот алгоритм включает в себя переборы различных возможных собственных разбиений заданной машины при отыскании минимального собственного разбиения. Эти переборы могут быть весьма громоздкими. Существуют алгоритмы, упорядочивающие подобные переборы (см., например, [149]). Существуют также «промежуточные» алгоритмы, которые, уменьшая переборы, позволяют получить результат лучший, чем при применении алгоритма Ауфенкампа, хотя и не гарантируют минимальности.

Вернемся теперь к нашим двум примерам (рис. 9.15 и 9.18).

Для машины рис. 9.15 разбиение на группы псевдоэквивалентных состояний является и минимальным собственным разбиением. Проверим это.

Обозначим группу буквой А, а группу буквой В. Проследим возможные переходы:

Рис. 9.20.

Рис. 9.21.

Рис. 9.22.

Теперь легко построить две минимальные машины для машины рис. 9.15, заменив состояние группы А состоянием , а состояния группы В состоянием . Одна из этих минимальных машин изображена на рис. 9.16, вторая — на рис. 9.20. Для машины рис. 9.18 также имеются два возможных минимальных собственных разбиения. Это разбиение и разбиение .

Диаграмма состояний минимальной машины, соответствующая первому собственному разбиению, изображена на рис. 9.21, а соответствующая второму — на рис. 9.22.