![]() |
АВТОМАТОВ АЛГЕБРАИЧЕСКАЯ ТЕОРИЯРасстановка ударений: АВТОМА`ТОВ АЛГЕБРАИ`ЧЕСКАЯ ТЕО`РИЯ АВТОМАТОВ АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ - направление в автоматов теории, характеризующееся использованием алгебраич. средств в изучении автоматов. А. а. т. основана на том, что автоматы можно рассматривать как нек-рые специальные алгебры или алгебраические системы. Кроме того, события, представимые конечными автоматами, относительно операций объединения, произведения и итерации образуют алгебру, порождаемую конечным множеством так наз. элементарных событий, каждое из к-рых состоит из одного однобуквенного или пустого слова. Алгебраический подход позволяет непосредственно использовать алгебраич. результаты в теории автоматов, а также помогает в нек-рых случаях установлению связи теории автоматов с другими областями математики. Так, с помощью теории автоматов были получены доказательства разрешимости нек-рых арифметических теорий второй ступени, а также новое, более простое, решение ограниченной Бернсайда проблемы.
С алгебраич. точки зрения, автомат (конечный или бесконечный) ai aj S = φ (φ (s, ai), aj).
Эта полугруппа наз. полугруппой автомата R = {(α, β): α, α ∈ A* и ∀ s ∈ S (φ (s, α) = φ (s, β))}. Для произвольного состояния s ∈ S конгруэнция R является максимальной подконгруэнцией отношения Rs = {(α, β): α, α ∈ A* и (φ (s, α) = φ (s, β))}.
Это означает, в частности, что событие, представимое инициальным акцептором Автомат (A, S, В, φ, ψ) наз. линейным автоматом (л. а.), если A, S и В - линейные пространства над нек-рым полем Р, φ (s, а) = φ1 (s) + φ2 (а), ψ (s, а) = ψ1 (s) + ψ2 (а), где φ1, φ2, ψ1, ψ2 - линейные отображения соответственно: S в S, А в S, S в В, А в В. Обычно предполагается, что поле Р конечно, а пространства A, S, В конечномерны; в этом случае л. а. является конечным автоматом. Если в представлении конечного акцептора в виде алгебры, операциями к-рой являются буквы входного алфавита, допустить многоместные операции, то полученное обобщение наз. автоматом над термами (автоматом над деревьями, обобщенным автоматом). Такие автоматы используются для доказательства разрешимости нек-рых математич. теорий второй ступени. Лит. : [1] Алгебраическая теория автоматов, языков и полугрупп, М., 1975; [2] Глушков В. М., «Успехи матем. наук», 1961, т. 16, №5, с. 3-62; [3] Тэтчер Д ж. В., Райт Д ж. Б., в кн. : Кибернетический сборник, в. 6, М., 1969, с. 112-44. См. также лит. к статье Автомат. В. Б. Кудрявцев, Ю. И. Янов. Источники:
|
![]()
|
|||
![]() |
|||||
© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник: http://mathemlib.ru/ 'Математическая библиотека' |