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

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

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

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

Если зафиксировать входной сигнал схемы (набор значений входных переменных), то применив ф-ции переходов и выходов компонентов схемы и приравняв значения переменных,

соответствующих отождествленным узлам, можно вычислить значения всех переменных, которые определят новое состояние и выходной сигнал. Если схема корректна, то новое состояние и выход определены однозначно. Одно из самых простых условий корректности схемы состоит в том, чтобы любой цикл (т. е. замкнутый путь, ведущий через компоненты по стрелкам, соединяющим узлы) содержал хотя бы одну компоненту, являющуюся Мура автоматом. В С. т. а. выходной сигнал автомата Мура, определяемый данным состоянием, относят обычно к тому же моменту автоматного времени, что и само состояние. Это позволяет избежать противоречий при вычислении значений переменных. Кроме того, каждый входной узел любой компоненты и каждый внеш. выходной узел должен быть связан или с выходным узлом некоторой компоненты, или с внеш. входным узлом. Применяют и другие, более слабые условия корректности схем.

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

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

Общих эффективных методов решения проблемы синтеза для произвольных полных систем автоматов в настоящее время не существует (не считая метода полного перебора).

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

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

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

Важную роль в С. т. а. играет задача оптим. синтеза, т. е. задача отыскания наилучшей (с точки зрения некоторого критерия) схемы, реализующей заданный автомат. Наиболее распространенным является критерий

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

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

К С. т. а. можно отнести также некоторые построения, рассматриваемые в теории автоматов бесконечных. Напр., автоматы итеративные, сети Неймана — Мура и т. п. представляют собой регулярные композиции бесконечного (или неограниченного конечного) числа экземпляров некоторого конечного автомата.

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464-469]; Кобринский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. М., 1962 [библиогр. с. 399—402]; Hartmanis J., Stearns R. Е. Algebraic structure theory of sequential machines. Englewood Cliffs, 1966 [библиогр. с. 206—208].

А. А. Легаичевский.