§ 9.4. Распознавание эквивалентности состояний в случае, когда ограничения наложены на длину входных последовательностей

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

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

Поскольку число различных символов конечно и длина последовательностей ограничена числом q, множество L содержит конечное число различных последовательностей.

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

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

Таким образом, в данном случае всегда существует алгоритм распознавания эквивалентности — алгоритм полного перебора. Одной из форм организации такого перебора является «возведение в степень» матрицы соединений исследуемой П-машины, подробно рассмотренное в § 3.6.

Напомним приведенные там свойства матрицы .

1. Элемент матрицы перечисляет все последовательности входных величин длины q, которые переводят машину из состояния в состояние , и соответствующие им выходные последовательности.

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

3. Любая входная последовательность длины q присутствует в каждой строке матрицы в одном из элементов этой строки.

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

Например, пусть множество L содержит следующие четыре последовательности:

а П-машина имеет диаграмму состояний, показанную на рис. 3.11, — матрица для нее была построена в § 3.6.

При этом отметки расставляются таким образом:

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

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

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

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

Пусть множество L содержит все последовательности длины, меньшей или равной q. Множество L составляет подмножество множества Е, содержащего все входные последовательности. Поэтому всякие два состояния, эквивалентные относительно множества Е (т. е. просто эквивалентные), эквивалентны также и относи тельно .

Возникает такой вопрос: в каких случаях разбиение всех состояний машины на группы эквивалентных состояний совпадает с разбиением всех состояний на группы эквивалентных относительно L, т. е. когда эквивалентные относительно L состояния являются эквивалентными и относительно Е? Если мы будем уметь отвечать на этот вопрос, то в тех случаях, когда ответ положительный (т. е. когда разбиения совпадают), мы можем применять простой алгоритм Ауфенкампа и Хона; в тех же случаях, когда ответ отрицательный (разбиения не совпадают), придется применять описанный выше перебор, либо искать какой-либо новый прием.

Ответ на поставленный вопрос связан с соотношением чисел k и q — числа состояний машины и максимальной длины допустимых входных последовательностей. Если длина q достаточно велика, то, как мы ниже установим, эта длина может оказаться достаточной для различения всех неэквивалентных состояний. Тогда всякая пара состояний, неэквивалентных относительно Е, будет неэквивалентна и относительно .

Пусть задана последовательностная машина S, имеющая k состояний. Проведем симметричное разбиение ее матрицы соединений С по методу Ауфенкампа и Хона. Тогда состояния машины разобьются на группы эквивалентных состояний. Пусть число этих групп будет (очевидно, ).

Докажем, что если то проведенное по методу Ауфенкампа и Хона разбиение состояний на группы эквивалентных состояний совпадает с разбиением состояний машины на группы эквивалентных относительно L состояний; тогда при нашу задачу будет решать алгоритм Ауфенкампа и Хона, и число групп будет равно .

Действительно, построим машину с числом состояний удовлетворяющую следующим требованиям: а) для каждого состояния машины S найдется эквивалентное состояние машины и, наоборот, для каждого состояния машины найдется эквивалентное состояние машины ; б) все состояния машины попарно неэквивалентны. В § 9.7 будет показано, что машину, обладающую указанными свойствами, всегда можно построить.

Воспользуемся теоремой Мура о наименьшей длине входной последовательности (эксперимента) для различения двух заданных начальных состояний П-машины (см. далее § 11.2). Эта теореме утверждает, что если машина N имеет k состояний и все состояния неэквивалентны друг другу, то для каждой пары состояний всегда найдется входная последовательность длины не более , которая эти состояния позволит различить.

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

Если же , то разбиение относительно L может не совпадать с разбиением относительно Е. Тогда разбиение относительно L приходится строить методом перебора, например возведением матрицы С в степень .

Кроме того, можно без труда оценить снизу число групп эквивалентных относительно L состояний, что также помогает в ряде случаев избежать перебора. Действительно, разобьем матрицу С на -матрицы только горизонтальными линиями (т. е. выделим в ней все группы строк, совпадающих с точностью до порядка элементов). Тогда состояния машины разбиваются на групп. Это будут группы состояний, эквивалентных относительно множества всех входных последовательностей длины (множество совпадает с алфавитом ). Ясно, что число групп эквивалентных относительно L состояний не может быть меньше чем , так как с L и, следовательно, всякие два состояния, эквивалентные относительно L, эквивалентны и относительно

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

Поэтому если окажется, что , несмотря на то, что , можно пользоваться алгоритмом Ауфенкампа и Хона.

При практическом применении алгоритма Ауфенкампа и Хона оба числа и получаются на различных этапах вычисления. Число получается уже на первом этапе, когда мы проводим горизонтальные линии раз биения матрицы С. Если проведенные затем вертикальные линии «испортили» разбиение, то приходится вновь проводить горизонтальные линии и т. д., и в итоге будет получено число .

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

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

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

Однако иногда вводят понятие, близкое к эквивалентности, а именно понятие совместимости состояний, определяемое следующим образом:

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

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

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

Понятие совместимости часто оказывается полезным; в частности, его можно применить для минимизации -машины, имеющей ограничения типа Ауфенкампа (см. § 9.8).