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

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

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

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

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

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

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

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

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

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

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

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