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

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

С алгебраической точки зрения, автомат (конечный или бесконечный) A=(A,S,B,φψ) является трехосновной алгеброй, т. е. алгеброй с тремя множествами A,S,B элементов и двумя операциями φ: S x A → S и ψ: S x A → B. С другой стороны, переходную систему (A,S,φ), где A={a₁,…, a_n} - входной алфавит, S - множество состояний (см. Автомат конечный), можно рассматривать как алгебру (S,a₁…,a_n) с унарными операциями, обозначаемыми буквами a_i входного алфавита A и такими, что a_i s_j= φ (s_j,a_i). Таким образом, для автоматов естественно определяются такие понятия, как автоматов гомоморфизм, изоморфизм, подавтомат и т. д. Вместе с тем этот подход позволяет сопоставить автомату A=(A,S,B,φ,ψ) полугруппу преобразований множества S с операцией суперпозиции, порожденную операциями a_i, так что для произвольных a_i,a_j из A и s из S положено

a_ia_jS= φ(φ(s,a_i),a_j).

Эта полугруппа называется полугруппой автомата A, она используется как средство описания определенных свойств автоматов (классификация, разложимость, изоморфизм и т. д.) на алгебраическом языке. В то же время всякой полугруппе с единицей можно сопоставить автомат с заданным входным алфавитом A={a1,…, an} и множеством состояний следующим образом. Каждой букве a_i из A ставят в соответствие некоторый элемент q_i из и тогда функцию переходов φ можно определить так: φ(q,a_i) = qq_i. Полугруппа такого автомата изоморфна подполугруппе полугруппы , порожденной элементами q₁,…,q_n и тем самым в случае, если q₁,…,q_n суть образующие полугруппы , полугруппа автомата изоморфна исходной полугруппе. Полугруппа автомата очевидным образом изоморфна факторполугруппе входной полугруппы всех слов в алфавите A (множество A*) с операцией последовательного соединения слов (конкатенация) по конгруэнции

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

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

Автомат (A,S,B,φψ) называется линейным автоматом (л. а.), если A,S и B - линейные пространства над некоторым полем P,

φ (s,a) = φ₁(s)+ φ₂(a), ψ (s,a) = ψ₁(s)+ ψ₂(a),

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

Лит.: [1] Алгебраическая теория автоматов, языков и полугрупп, M., 1975; [2] Глушков В.М., <<Успехи матем. наук>>, 1961, т. 16, №5, с. 3-62; [3] Тэтчер Дж.В., Райт Дж.Б., в кн.: Кибернетический сборник, в. 6, М., 1969, с. 112-44. См. также лит. к статье Автомат.