АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ АВТОМАТОВ

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

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

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

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

Точным определением преобразования информации, выполняемой автоматом, служит определение отображения, индуцируемого состоянием автомата. Для того, чтобы сформулировать это определение, рассмотрим свободные полугруппы F (X) и F (Y), порожденные мн-вами X и У, т. е. мн-ва слов в алфавитах X и Y. Эти полугруппы наз. входной и выходной полугруппой автомата, соответственно. Распространим ф-ции переходов и выходов на полугруппы F (X) и F (У), полагая пустое слово), где . Отображение определяемое равенством отображением (оператором), индуцируемым состоянием а автоматах. Говорят также, что отображение представлено в автомате А состоянием а. В некоторых случаях в автомате фиксируют начальное состояние. Такие автоматы наз. инициальиыми, а говоря об отображении, представленном в инициальном автомате,

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

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

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

К понятию представления отображений в автоматах близко примыкает понятие представления событий. Событием в алфавите произвольное мн-во слов полугруппы F (X). Говорят, что событие S представлено в Х-Y-автомате А выходным сигналом (мн-вом выходных сигналов ) при начальном состоянии а, если где тогда и только тогда, когда

Система событий состоящих из слов , таких, что однозначно определяет отображение . Если , то события представлены выходными сигналами автомата А при начальном состоянии а. Поэтому часто вместо представления отображений рассматривают представление событий. В автоматах Мура представление событий мн-вами выходных сигналов сводится к представлению их мн-вами состояний. Событие 5 представлено в автомате А мн-вом состояний . А при начальном состоянии , если тогда и только тогда, когда

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

Важную роль в А. т. а. играет связь автоматов с полугруппами. Каждый входной сигнал автомата А определяет преобразование мн-ва состояний автомата А. Полугруппа G А, порожденная всеми такими преобразованиями, наз. полугруппой автомата А. Обычно к полугруппе GA добавляют единицу — тождественное преобразование , рассматривая его как преобразование, индуцируемое пустым словом. Для каждого слова можно определить преобразование Соотношение показывает, что отображение есть гомоморфизм свободной полугруппы F (X) на полугруппу Полугруппу автомата А можно рассматривать как Х-автомат, если считать Отображение , определенное равенством является гомоморфизмом автомата GA в автомат А. тоже можно рассматривать как Х-автомат с ф-цией переходов автомат, порожденный состоянием . Тогда у будет гомоморфизмом автомата F (X) на Гомоморфизмы у и индуцируют разбиения R и полугруппы F (X) на классы слов, имеющих одинаковые образы при гомоморфизмах у и соответственно. Разбиение является автоматным, т. е. для любого класса 5 этого разбиения и любого найдется класс S такой, что Это разбиение определяет отношение конгруэнтности на автомате фактор-автомат по которому изоморфен подавтомату автомата А, порожденному состоянием а (он состоит из всех состояний

вида , где ). Разбиение R является полугрупповым, т. е. для любой пары S и S" его классов найдется класс S такой, что Это разбиение определяет отношение конгруэнтности на полугруппе F (X) и фактор-полугруппа по этому отношению изоморфна полугруппе GA. Если автомат А порождается состоянием а, т. е. , то является макс. полугрупповым разбиением, вписанным в разбиение . В общем же случае R есть максимальное полугрупповое разбиение, вписанное во все разбиения .

Понятие полугруппы автомата можно использовать для классификации автоматов по свойствам их полугрупп. При этом полугруппа рассматривается как абстрактная полугруппа (а не полугруппа подстановок). Говорят, что автомат А принадлежит полугруппе G, если его полугруппа изоморфна G. Фиксируя некоторый класс полугрупп, можно получить класс автоматов, принадлежащих этим полугруппам. Напр., коммутативные автоматы — это автоматы, принадлежащие коммутативным полугруппам, групповые автоматы — это автоматы, принадлежащие группам. Конечные автоматы и только они принадлежат, очевидно, конечным полугруппам. Разбиение состоит, как видно из определения, из событий, представленных различными состояниями в автомате А при начальном состоянии а. Для любой системы М событий в алфавите X можно построить систему К разбиений и макс. автоматное разбиение R, вписанное во все разбиения системы К. Оно определит (единственным образом) автомат, в котором представлены все события системы К. Будем говорить, что система К принадлежит полугруппе, которая совпадает с полугруппой построенного так автомата. Эта полугруппа определяется максимальным полугрупповым разбиением, вписанным во все разбиения системы К.

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

Важную роль в автоматов теории играет понятие автомата недетерминированного, т. е. автомата, у которого ф-ции переходов и выходов являются многозначными. Для недетерминированных автоматов применяется следующая терминология: если , то говорят, что автомат А может перейти под действием входного сигнала из состояния а в состояние b. Аналогично определяется возможность перехода под действием входного слова. Для недетерминированных автоматов можно определить понятие представления события следующим образом. Пусть А — недетерминированный Х-автомат, Событие, представимое в А при мн-ве начальных состояний и мн-ве А заключительных состояний совпадает с мн-вом всех слов, под действием которых автомат может перейти из мн-ва .

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

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

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

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

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

В связи с применением теории автоматов к теории матем. машин важное значение имеет понятие многорегистрового автомата (см. Автомат регистровый) как бесконечного автомата специального типа, удобного при изучении операционных устройств вычисл. машин. Это понятие играет центр, роль нового направления в теории автоматов — дискретных преобразователей теории. В этой теории изучается взаимодействие двух автоматов — конечного управляющего и бесконечного операционного автомата. Автомат управляющий задает некоторое преобразование, определенное на мн-ве состояний операционного автомата. Преобразования, задаваемые таким образом, можно рассматривать как элементы спец. микропрограммной алгебры. Использование соотношений этой алгебры позволяет выполнять оптимизацию управляющего автомата. Важную роль при этом играет полугруппа операционного автомата, которая лежит в основе микропрограммной алгебры. Именно наличие соотношений в этой полугруппе и позволяет производить наиболее глубокие преобразования управляющих автоматов. Лит.: Глушков В. М. Абстрактная теория автоматов. «Успехи математических наук», 1961, т. 16, в. 5; Глушков В. М. Теория автоматов и формальные преобразования микропрограмм. «Кибернетика», 1965, № 5; Е1gоt С. С., Mezei J. Е. On relations defined by generalized finite automata. «IBM journal of research and development», 1965, v. 9, Nl;Glushkov V. М., Letichevskii A. A. Theory of algorithms and discrete processors. В кн.: Advances in information systems science, v. 1. New York, 1969. В. М. Глушков, А. А. Летичевский.