АБСТРАКТНАЯ ТЕОРИЯ АВТОМАТОВ

— направление в автоматов теории, характеризующееся тем, что при изучении автоматов отвлекаются от их структурных особенностей. При таком подходе внутр. состояния автомата, его входные и выходные сигналы рассматриваются как некие абстрактные символы, образующие соответственно алфавиты: Q (внутренний), X (входной), Y (выходной). X и Y считаются конечными алфавитами, Q может быть бесконечен. Автомат детерминированный определяется как , где ф-ция переходов W отображает в Q, а ф-ция выходов Ф отображает в Y. Автомат недетерминированный определяется аналогично, но с той лишь разницей, что в качестве допускаются многозначные ф-ции. В случае же автомата вероятностного под Т и Ф следует понимать матрицы переходных и выходных вероятностей, т. е. ф-ции, отображающие в числовой промежуток (0, 1) и имеющие, соответственно, смысл вероятность того, что входной символ переводит состояние в состояние вероятность того, что при входном символе и внутр. состоянии будет выработан выходной символ

Приведенные понятия весьма общи и не конструктивны в случае, когда Q бесконечен. Более узкие классы могут быть выделены путем наложения различных ограничений на компоненты Q, X, Y, W, Ф. Поскольку эти ограничения не формулируются в структурных терминах, то они касаются гл. о. мощности алфавитов (напр., если Q конечен, то и автомат наз. конечным) или общих свойств функций Ф. В случае вырождения, когда тот или иной алфавит состоит из одного символа, удобнее рассматривать модифицированные определения, которые получаются при удалении вырожденных компонент. Напр., детерминированный автомат без выхода — это тройка Ч, где имеют прежний смысл; вероятностный автомат автономный — это пара Р), где W — матрица переходных вероятностей для состояний из Q (т. е. по существу такой автомат является цепью Маркова).

В А. т. а. изучаются преимущественно такие концепции поведения (см. Поведение автоматов), в которых преобразуемыми или принимаемыми словами являются слова в алфавите X (входные слова), а результатами преобразования или порождения являются слова в алфавите Y (выходные слова). В основном это — реализация операторов в автомате и представление множеств в реальное время. В силу большой общности и неконструктивности употребляемых понятий автомата, даже в случае детерминированных автоматов, реализуемые операторы (представляемые мн-ва) могут оказаться неэффективными. В А. т. а. осн. изучаемыми конструктивными объектами являются автоматы конечные, а также реализуемые ими операторы и представляемые ими мн-ва (конечно-автоматные операторы и мн-ва). В А. т. а. широко применяются методы и понятия алгебры, логики математической и алгоритмов теории. Центр, проблемами А- т. а., которые порождены практическими задачами конструирования и эксплуатацив вычислительной техники и получили далеко идущее теоретическое развитие, являются проблемы синтеза и анализа, а также связанная с ними теория экспериментов с автоматами.

Анализ и синтез автоматов в А. т. а. Проблема синтеза заключается в поиске и построении автомата, исходя из условий, предъявляемых к реализуемому им оператору или к представляемому им мн-ву, причем в А. т. а. гл. о. имеются в виду реализация или представление в реальное время. Обычно предполагается, что эти условия выражены на достаточно четком и формализованном языке (т. н. язык заказчика), напр, в виде формулы 21 этого языка. Кроме того, считается, что искомый автомат принадлежит заранее очерченному классу автоматов, допускающих конструктивное описание. Формальный язык, средствами которого осуществляется это описание (язык исполнителя), также считается заданным. Когда речь идет о конечных автоматах, обычно, описание автомата заключается в представлении системы его команд посредством графического или табличного задания функций (матриц переходных и выходныхвероятностей, если автомат вероятностный). Построенный в результате абстрактного синтеза автомат может быть использован впоследствии как исходный материал на этапе синтеза автомата структурного.

В рамках общей проблемы абстрактного синтеза возникают отд. более частные проблемы:

1) Существование. Существует ли оператор, удовлетворяющий условию, выраженному формулой 21, и реализуемый (мн-во представимое) в автомате данного типа?

2) Единственность. Единственен ли этот оператор? 3) Конструкция. Для к.-н. оператора, удовлетворяющего условию 21, построить реализующий его автомат и указать соответствующую настройку: начальное состояние, заключительные состояния, а в случае вероятностного автомата—допустимый уровень надежности. 4) Минимизация. Построенный автомат ЗЛ привести посредством эквивалентных преобразований к эквивалентному ему автомату, удовлетворяющему

некоторым критериям оптимальности. Напр., в случае конечных автоматов — минимизация числа состояний путем склеивания неразличимых и устранения недостижимых состояний.

Решение указанных проблем мыслится в виде алгоритмов, которые по заданной формуле 91 доставляют ответы на вопросы 1)- 2) и осуществляют необходимые конструкции и преобразования для проблем 3)-4). Соответствующая теория существенно зависит от языков, употребляемых заказчиком; в качестве языка исполнителя обычно рассматриваются различные классы автоматных диаграмм. При выборе языка заказчика естественно руководствоваться следующими двумя (антагонистичными) требованиями: выразительность языка, т. е. удобство (для заказчика) изложения в нем условий, предъявляемых к поведению проектируемого автомата; простота алгоритмов, решающих проблему синтеза в целом и отдельные ее задачи. (Аналогия: в теории программирования — выразительность входного языка и простота транслятора). Эта ситуация подробно исследована применительно к конечным автоматам. G точки зрения простоты алгоритмов предпочтительны алгебр, языки (см. Регулярные события и выражения). Более выразительными являются языки, основанные на применении фрагментов логики предикатов (см. Язык логический для задания автоматов), но и алгоритмы синтеза для них становятся более громоздкими.

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

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

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

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

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464-469]; Бюхи Д. Р.

О разрешающем методе для ограниченной арифметики второго порядка. В кн.: Кибернетический сборник, в. 8. М., 1964; Цетлин М. Л, Исследования по теории автоматов и моделированию биологических систем. М., 1969 [библиогр. с - 306—316]; Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (Поведение и синтез). М., 1970 [библиогр. с. 389—395]. Б. А. Трахтенброт.