ЯЗЫК АНКЕТНЫЙ

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

Диалог начинается с того, что «исполнитель» просит «заказчика» назвать входной и выходной алфавиты задуманного им автомата. Далее допускаются вопросы следующих двух типов. Вопросы 1-го типа состоят в том, что «исполнитель» называет пару слов где слово во входном алфавите, у — слово в выходном алфавите, имеющее такую же длину, как х, и спрашивает «заказчика», существует ли такое состояние, при котором (как начальном) задуманный им автомат перерабатывает слово х в слово у. Вопросы 2-го типа состоят в том, что «исполнитель» называет последовательность пар слов где слово во входном алфавите, слово в выходном алфавите, имеющее такую же длину, как и спрашивает «заказчика», существует ли такое состояние, при котором (как начальном) задуманный им автомат перерабатывает слово слово слово хп - в уп. В частности, если последовательность пар слов такова, что то ответ на данный вопрос очевидно должен быть отрицательным, т. к. невозможен автомат, который при одном и том же начальном состоянии одинаковые входные слова перерабатывает в различные выходные слова. На каждый вопрос «заказчик» должен дать положительный или отрицательный ответ. Совокупность всех таких вопросов и ответов на них условно наз. анкетным языком.

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

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

Лит.: Таль А. А. Анкетный язык и абстрактный синтез минимальных последовательностных машин. «Автоматика и телемеханика», Э. Ф. Умозрительные эксперименты с последовательностными машинами. В кн.: Автоматы. Пер. с англ. М., 1956; Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (Поведение и синтез). М., 1970 [библиогр. с. 389—395]. Я.М. Барздинь.