ЭКСПЕРИМЕНТЫ С АВТОМАТАМИ

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

Точнее, понятие эксперимента по существу совпадает с понятием вычислимого функционала. Пусть зафиксирован некоторый класс автоматов инициальных со входным алфавитом X и выходным алфавитом У. Введем следующие обозначения: — совокупность всех конечных мн-в слов в алфавите — совокупность всех конечных мн-в пар слов вида где слово в алфавите X, а у — слово в алфавите Y. Если и , то — элемент из , состоящий из всех тех вида что , а у — слово, в которое А перерабатывает х.

Формальное определение эксперимента следующее: это тройка где — мн-во конструктивных объектов, называемое мн-вом априорных информаций (в качестве элементов могут быть, напр., таблицы переходов автоматов, мн-ва таких таблиц и т. п.), Q — мн-во конструктивных объектов, называемое мн-вом заключений (в качестве элементов Q могут быть, напр., таблицы переходов с отмеченным начальным состоянием), F — эффективная функция от двух аргументов бит], где принимающая значения как из так и из (предполагается, что .

1. Схема простого эксперимента.

2. Схема кратного эксперимента.

3. Схема безусловного эксперимента.

4. Схема условного эксперимента.

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

и осуществляется шаг . Находится . Если , то и процесс останавливается. Если находится и осуществляется шаг .

Классификация экспериментов. Эксперименты можно классифицировать по числу требуемых для их проведения экземпляров (копий) исследуемого автомата (один автомат наз. копией другого, если оба автомата имеют одинаковые таблицы переходов и находятся в одном и том же состоянии перед началом эксперимента). А именно: 1) простые эксперименты (рис. 1), когда требуется единственный экземпляр автомата (т. е. слова из являются продолжением друг друга); 2) кратные эксперименты, когда требуется более нем один экземпляр автомата (рис. 2).

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

Эксперименты еще можно классифицировать по виду зависимости от предыстории процесса — на 1) безусловные (однородные, неразветвленные) эксперименты (рис. 3), когда прикладываемая входная последовательность (или последовательности в случае кратного эксперимента) полностью определена заранее (т. е. функция F зависит только от 1-го аргумента 6), и 2) условные (неоднородные, разветвленные) эксперименты (рис. 4), когда каждый последующий символ прикладываемой входной последовательности (или последовательностей в случае кратного эксперимента) экспериментатор выбирает в зависимости от поданных ранее входных последовательностей и полученных выходных последовательностей (т. е. функция F существенно зависит от 2-го аргумента ).

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

Основные задачи. 1. Диагностическая задача. Известно, что данный автомат А, таблица переходов которого имеется у нас, находится в одном из состояний Найти это состояние.

2. Установочная задача. Известно, что автомат А, таблица переходов которого имеется, находится в одиом из состояний Установить А в известное состояние. Множество состояний одно из которых, как известно экспериментатору, является начальным, наз. мн-вом допустимых состояний. Диагностическая задача, следовательно, является задачей определения начального состояния А, а установочная состоит в определении конечного состояния А. Эксперимент, который решает диагн. задачу, наз. диагностическим, а эксперимент, решающий установочную задачу, — установочным. Диагн. задача ставится и для простых, и для кратных экспериментов; установочная же имеет смысл только для простых экспериментов.

3. Задача расшифровки (распознавания) автоматов имеет несколько вариантов. Рассмотрим основные из них. а) Задача распознавания автоматов из заданного класса. Известно, что автомат А, как неинициальный, принадлежит заданному конечному классу М неинициальных автоматов. Требуется определить этот автомат (т. е. среди автоматов класса М выделить тот, который совпадает с А), б) Задача инициальной расшифровки автоматов не более чем с к состояниями. Известно, что инициальный автомат А с заданными входным и выходным алфавитами имеет не более к состояний. Требуется определить инициальный автомат (напр., в виде таблицы переходов с отмеченным начальным состоянием), в котором реализован тот же оператор, что и в автомате А. в) Задача остаточной расшифровки автоматов не более, чем с к состояниями, заключается в том, чтобы с помощью подходящего простого эксперимента Е определить инициальный автомат, в котором реализовав тот же оператор, что и в автомате А с начальным состоянием, в которое он перешел после эксперимента Е. Если А является сильно связным приведенным автоматом, то остаточная расшифровка для А означает по существу не что иное, как определение его таблицы переходов (с точностью до нумерации состояний) с помощью простого эксперимента. Общая задача остаточной (инициальной) расшифровки автоматов отличается от предыдущих задач тем, что заранее неизвестна верхняя оценка числа состояний

автомата А, а заданы только входной и выходной алфавиты.

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

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

Класс автоматов исключительным, если ни одно состояние любого автомата не эквивалентно никакому состоянию автомата Если известно, что автомат А принадлежит исключительному классу автоматов где А; имеет состояний, то автомат А может быть распознан простым безусловным экспериментом длины l, где

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

Пусть для любых то, означает некоторое мн-во (быть может, мн-во всех) автоматов с фиксированными -буквенным входным и -буквенным выходным алфавитами и А состояниями и — мн-во тех автоматов из , которые обладают заданным свойством Е. Утверждают, что почти все автоматы из обладают свойством Е, если

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

Легко видеть, что невозможен эксперимент, который для всех (даже для почти всех) автоматов решил бы общую задачу инициальной (остаточной) расшифровки. Однако имеет место следующее. Пусть , как и выше, мн-во всех автоматов с заданными то, . Утверждают, что с частотой автоматы обладают заданным свойством Е, если в для всех к. Тогда для любого существует кратный (простой) эксперимент, который с частотой 1 — в решает общую задачу инициальной (остаточной) расшифровки. При этом высота (длина) соответствующего кратного (простого) эксперимента оказывается относительно небольшой — порядка к (порядка ), где k — число состояний того «черного ящика», к которому применяется данный эксперимент.

Лит.: . Я. М. Барздинь.