§ 11.4. Изучение последовательностных машин с помощью простых экспериментов

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

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

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

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

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

Теорема 2 (Мура — Карацубы). Для определения последнеф состояния заданной П-машины с k неэквивалентными внутренними состояниями достаточно провести эксперимент длиной не более конечного автомата — длиной не более .

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

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

До начала эксперимента, при , это условие выполнено.

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

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

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

Таким образом, каждое имеет длину не больше s, и для определения последнего состояния потребуется эксперимент длины не более

для П-машин и

для конечного автомата.

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

Рис. 11.7.

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

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

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

Рис. 11.8.

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

Для автомата без преобразователя получаем очевидную оценку, равную единице.

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

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

(11.10)

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

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

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

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

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

Пример 4. Рассмотрим конечный автомат с выдодным преобразователем, имеющий диаграмму состояний (рис. 11.9), основную таблицу и таблицу преобразователя (табл. 11.6 и 11.7).

В табл. 11.8 показан процесс построения кратчайшего эксперимента для определения последнего состояния автомата.

Рис. 11.9.

Так как в примере рассматривается автомат, то в соответствии с доказательством теоремы 2 для каждого мы выбираем такие входные последовательности длиной , которые различают какие-либо два состояния множества и берем первые s символов этих последовательностей (последние 1-е символы в таблице зачеркнуты). Как показано в четвертом замечании к теореме 2, в этом примере можно от перейти прямо к , минуя . Для различения двух предпоследних состояний достаточно. одного любого входного символа. Поэтому общий эксперимент, определяющий конечное состояние рассматриваемого автомата, будет или , и длина его равна 11.

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

Таблица 11.6

Таблица 11.7.

При отыскании оценки длины такого эксперимента и при построении самого эксперимента возможны два подхода.

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

Таблица 11.8.

За этими последовательностями следуют последовательности, различающие эти последние состояния между собой. Такой подход предложен в работе Мура [72]. Если рассматривается множество П-машин с числом внутренних состояний , то оценка длины такого эксперимента из (11.3) и (11.7) будет

где — максимальные числа состояний.

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

Для конечного автомата с преобразователем из (11.4) и (11.9) получим

(11.14)

или при всех , равных между собой,

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

(11.16)

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

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

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

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

В противном случае исключаем эти машины из рассмотрения.

3. Проводим эксперимент с соответствующей машиной (или с машинами при всех возможных начальных состояниях (умозрительно) , с машиной (в действительности), а также (умозрительно) с или с теми из машин которые не исключены в п. 1, считая начальными стояниями машин или состояния, определяющиеся последними их состояниями и последним; символом эксперимента . Исключаем из рассмотрения те из машин , для которых результаты эксперимента не совпадают с результатами эксперимента с машиной , и устанавливаем последние состояния остальных машин.

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

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

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

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

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

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

Рис. 11.10.

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

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

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

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

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

(11.17)

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

(11.18)

для автоматов без преобразователей, или же при

Можно показать, что оценки (11.17) — (11.19) длины неразветвленного эксперимента, полученные исходя из объединения всех машин множества, всегда хуже оценок (11.13), (11.15) и (11.16) длины разветвленного экспег римента, полученных по первому способу — приведением каждой из машин множества в определенное состояние и сравнением этих состояний. Кроме того, использование - второго способа для построения самого эксперимента значительно сложнее, чем применение первого способа, так как при отыскании отдельных последовательностей, составляющих этот эксперимент, приходится рассматривать не отдельные машины множества, а все множество в целом.