§ 11.2. Определение эквивалентности состояний последовательностных машин по реакции машины на входные последовательности конечной длины

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

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

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

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

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

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

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

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

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

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

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

при которой выходные последовательности не совпадают. Теорема доказана.

По поводу доказанной теоремы Мура сделаем несколько замечаний.

Замечание первое. Если рассматривается автомат с выходным преобразователем и известно не только число k неэквивалентных состояний, но и число I символов в таблице выходного преобразователя, то вместо оценки будет оценка

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

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

Пример. Рассмотрим конечный автомат с выходным преобразователем, диаграмма состояний которого имеет вид, показанный на рис. 11.3. Основная таблица автомата (табл. 11.1) и преобразователя (табл. 11.2) приведены ниже.

Рис. 11.3.

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

Таблица 11.1

Таблица 11.2

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

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

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

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

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

Рис. 11.4.

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

Пример. Рассмотрим конечный автомат с выходным состояний которого изображена на рис. 11.4, а основная таблица автомата и таблица преобразователя приведены ниже (в табл. 11.3 и 11.4).

Таблица 11.3

Таблица 11.4

Здесь для различения состояний и нужно, чтобы последовательность входных символов начиналась с , для различения же состояний и из нужно, чтобы входная последовательность начиналась с

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

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

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

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

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

Если , то получаем соответственно оценки для П-машин

и для автоматов с преобразователями

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

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

Рис. 11.5.