ГЛАВА 4

ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ СОСТОЯНИЙ

4.1. Введение

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

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

) Материал этой главы частично основывается на работах; Мура (Е. F. Moor, Qedanken - Experiments on Sequential Machines, «Automata Studies*, pp. 129-153, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: Э. Ф. Мур, Умозрительные эксперименты с последовательностными машинами. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956), Гинзбурга (S. О i п s b и г g. On tlie Lengtli of tlie Smallest Uniform Experiment Which Distinguishes the Terminal States of

4.2] КЛАССИФИКАЦИЯ ЭКСПЕРИМЕНТОВ 123

4.2. Классификация экспериментов

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

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

1. Безусловные эксперименты, когда прикладываемая входная последовательность полностью определена заранее.

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

Безусловный эксперимент, как правило, легче осуществить, чем условный: последний требует ряда промежуточных решений перед принятием окончательного, тогда как первый не требует таковых. Рассматривая человека или механический «генератор входной последовательности», чья функция состоит в подаче на автомат требуемых входных последовательностей, можно видеть, что в безусловных экспериментах генератор должен обеспечить единственную последовательность. В условных экспериментах генератор, помимо этого, должен быть способным вырабатывать ряд подпоследовательностей, причем каждая подпоследовательность основана на информации, поступающей в обратном направлении с выходных полюсов автомата. Как мы увидим, преимущество некоторых условных экспериментов состоит в том, что они

а Machine, J. Assoc. Comput. Mach., vol. 5, pp. 266-280, 1958. Русский перевод: С. Гинзбург, О длине кратчайшего однородного эксперимента, устанавливающего конечные состояния машины, «Кибернетический сборник» № 3, ИЛ, 1961) и Гилла (А. Oil 1, State Identification Experiments in Finite Automata, Information and Control, vol. 4, pp, 132-154, 1961).

относительно короче; кроме того, в некоторых случаях условные эксперименты легче построить, чем безусловные. Схематическое представление двух типов экспериментов показано на рис. 4.1.

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

Рис. 4.1. а) Безусловный эксперимент, б) Условный эксперимент.

находятся в одном и том же состоянии перед началом эксперимента. Эксперименты могут быть классифицированы по числу требуемых для их проведения экземпляров *) исследуемого автомата.

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

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

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

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

) В тексте оригинала употреблено слово «копия». Здесь и далее это слово заменено словом «экземпляр». {Прим. перев.)