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

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

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

Пусть задана любая П-машина. Выпишем ее матрицу соединений. Например:

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

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

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

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

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

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

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

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

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

В этом примере -матрицами являются две нижние — левая и правая — подматрицы.

Левая верхняя подматрица не является -матрицей, так как в третьей ее строке есть пара , которой нет в остальных строках. Аналогично обстоит дело и с верхней правой подматрицей.

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

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

В общем случае описанный процесс симметричногс разбиения на 1-матрицы закончится в конечное число шагов одной из двух ситуаций:

1. Разбиение тривиально, т. е. все подматрицы этого разбиения являются матрицами порядка 1 X 1 (линии разбиения оказываются в этом случае проведенными между всеми строками и столбцами).

2. Имеется нетривиальное разбиение, т. е. среди всех подматриц симметричного разбиения есть хоть одна матрица порядка , где .

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

Так, в нашем примере состояния разбиваются на три группы: .

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

Доказательство достаточности. Пусть матрица С может быть нетривиально симметрично разбита на 1-матрицы. Рассмотрим сначала простой случай, когда матрица имеет вид

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

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

Рассмотрим произвольную входную последовательность

Пусть -первый входной символ в этой последовательности, который не входит в .

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

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

Последовательность (9.1) была взята произвольно и, следовательно, состояния эквивалентны.

Рассмотрим теперь общий случай. Пусть матрица С симметрично разбита на -матрицы

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

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

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

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

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

Рис. 9.3.

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

1) Ветвь с первым индексом , отходящая от кружка , подходит к одному из кружков .

2) От кружка ветвь с первым индексом отходит к одному из кружков , например к кружку

3) Ветвь с первым индексом идет от кружка к кружку .

Покажем, что может иметь место только случай 3). Для этого докажем, что случаи 1) и 2) невозможны.

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

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

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

Предположим, что стрелки с первым индексом идут соответственно случаю 2). Тогда при подаче символа состояние переходит в состояние , а состояние — в состояние Но не эквивалентно ; следовательно, аналогично случаю 1) найдется последовательность такай, что выходная последовательность машины при подаче на вход этой последовательности будет зависеть от того, с какого из состояний — или — начала работу машина. Но тогда последовательность устанавливает неэквивалентность состояний и из, что противоречит условию. Следовательно, и случай 2) не имеет места. Итак, если, как это рассмотрено в нашем примере, от кружка отходит ветвь с первым индексом к кружку , и от всех кружков . к кружку также идут ветви с первым индексом (рис. 9.4).

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

Рис. 9.4.

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

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

Из доказанного следует, что матрица соединений рассматриваемой машины будет иметь вид

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

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

Доказанная теорема Ауфенкампа и Хона дает простой и очень удобный алгоритм определения всех групп эквивалентных состояний заданной П-машины. Алгоритм этот сводится к построению симметричного разбиения матрицы соединений С заданной П-машины.