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

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

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

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

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

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

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

Алгоритм построения диаграммы состояний -связной машины следующий:

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

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

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

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

Рис. 11.6.

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

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

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

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

Таблица 11.5

Продолжение табл. 11.5.