ГЛАВА XI. ОПРЕДЕЛЕНИЕ СВОЙСТВ ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН ПО ИХ РЕАКЦИИ НА ВХОДНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ КОНЕЧНОЙ ДЛИНЫ

§ 11.1. Основные определения и постановка задачи

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

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

Факт подачи на вход П-машины последовательности конечной длины мы будем называть экспериментом длины .

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

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

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

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

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

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

Пусть имеется П-машина S с k внутренними состояниями (число k нам ), с которой мы проводим конечный эксперимент длины .

Рис. 11.1.

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

Пусть, например, с конечным автоматом А с выходным преобразователем, диаграмма состояний которого показана на рис. 11.1, мы проводили эксперименты . длины . Легко видеть, что автомат В, диаграмма состояний которого показана на рис. 11.2, при и при начальных состояниях или будет выдавать на выходе ту же последовательность , что и автомат , и, таким образом, эти автоматы при не отличаются. Их отличие проявится только тогда, когда на вход будет подан следующий (четвертый) входной символ.

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

Рис. 11.2.

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

а) определение эквивалентности некоторых двух состояний одной и той же или двух разных П-машин;

б) определение эквивалентности двух П-машин;

в) определение диаграммы состояний П-машины;

г) определение, в каком состоянии находилась Я-машина в начале эксперимента, или приведение ее в определенное состояние к концу эксперимента и т. д.

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

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