Автоматов Алгебраическая Теория

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

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

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

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

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