ЯЗЫК ЛОГИЧЕСКИЙ для задания автоматов

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

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

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

При двоичном кодировании информации канонические уравнения конечного автомата принимают вид

где зависят от натурального аргумента t (интерпретируемого как дискретное время) и принимают лишь два значения: выражения алгебры логики от переменных

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

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

связывающий числовой аргумент t, и предикатные кванторы, связывающие одноместные предикатные переменные.

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

Легко видеть, что в И определимы следующие «вторичные» отношения и операции: равенство термов; отношение порядка для термов; ограниченные предметные кванторы, напр., каждого , меньшего t, справедливо предметные кванторы типа бесчисленного множества значений числового аргумента t соответственно — для всех значений t, за исключением, быть может, конечного их числа) справедливо . Поэтому и т. п. можно применять наряду с первичными средствами, перечисленными в а) — е). Напр., каждая из формул

формулирует условие, связывающее единственный выходной предикат Y с двумя входными предикатами

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

Легко понять, что указанный логический язык выразительнее языка регулярных выражений и др. языков синтеза, но вместе с тем большая выразительность требует значительного усложнения алгоритмов синтеза. Необходимо осторожно подходить к попытке дальнейшего расширения языка и усиления его выразительности, ибо зачастую это приводит к тому, что алгоритм синтеза уже в принципе невозможен (напр., если к термам отнести и суммы вида , где оба слагаемых — переменные величины). С другой стороны, для некоторых более узких фрагментов языка И возможны и более эффективные алгоритмы. Применение Я. л. оказалось полезным и для решения задач, возникающих в математической логике.

Лит.: Грахтенброт Б. А., Барздинь Я. М. Конечные автоматы (Поведение и синтез). М., 1970 [библиогр. с. 389—395]; Клини С. К. Представление событий в нервных сетях и конечных автоматах. В кн.: Автоматы. Пер. с англ. М., 1956; Бюхи Д. Р. Слабая арифметика второго порядка и конечные автоматы. В кн.: Кибернетический сборник, М. М.. 1964. Б. А. Трахтенброт.