Математическая энциклопедия - автоматов алгебраическая теория

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

С алгебраич. точки зрения, автомат (конечный или бесконечный) является трехосновной алгеброй, т. е. алгеброй с тремя множествами элементов и двумя операциями : X С другой стороны, переходную систему где входной алфавит, множество состояний (см. Автомат конечный), можно рассматривать как алгебру с унарными операциями, обозначаемыми буквами а i входного алфавита Аи такими, что Таким образом, для автоматов естественно определяются такие понятия, как автоматов гомоморфизм, изоморфизм, подавтомат и т. д. Вместе с тем этот подход позволяет сопоставить автомату полугруппу преобразований множества S с операцией суперпозиции, порожденную операциями а i , так что для произвольных из Аи s из S положено

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

Для произвольного состояния конгруэнция Rявляется максимальной подконгруэнцией отношения

Это означает, в частности, что событие, представимое инициальным акцептором является объединением нек-рых R-классов. Поскольку полугруппа автомата характеризует его с точностью до изоморфизма, то различным классам полугрупп соответствуют свои классы автоматов. В том случае, когда полугруппа автомата является свободной, или абелевой, или циклической, или нильпотентной и т. п., или, наконец, группой, автомат называется, соответственно, свободным, абелевым, циклическим, нильпотентным, групповым (или перестановочным). Другой подход, связанный с алгебраич. классификацией функций переходов и выходов, приводит к классам линейных, подстановочных и др. автоматов (см. Автомат). Подстановочные автоматы реализуют взаимно однозначные функции и используются в теории кодирования. Линейные автоматы представляют интерес в связи с простотой их схемной реализации.

Автомат наз. линейным автоматом (л. а.), если A, S и В - линейные пространства над нек-рым полем Р,

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

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985