АВТОМАТОВ АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ это:

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

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

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


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


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


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

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


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



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

Смотреть что такое "АВТОМАТОВ АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ" в других словарях:

  • Автоматов теория —         часть теоретической кибернетики (См. Кибернетика), объектом исследования которой являются различные преобразователи дискретной информации; возникла в начале 50 х гг. 20 в. в связи с требованиями практики проектирования вычислительных… …   Большая советская энциклопедия

  • ПОЛИГОН — над моноидом R, R полигон, операнд, непустое множество с моноидом операторов. Точнее, непустое множество Аназ. левым П. над моноидом К, если для любых и определено произведение , причем и 1а=а для любых . Правый П. определяется аналогично.… …   Математическая энциклопедия

  • АВТОМАТ — управляющая система, являющаяся автоматом конечным или некоторой его модификацией, полученной путем изменения компонент или функционирования. Основное понятие конечный А. возникло в середине 20 в. в связи с попытками описать на математическом… …   Математическая энциклопедия

  • АВТОМАТА ПОВЕДЕНИЕ — математическое понятие, описывающее взаимодействие автомата с внешней средой. Так, для автомата конечного внешней средой обычно является множество входных слов, а поведением словарная функция, реализуемая автоматом, или событие (иногда… …   Математическая энциклопедия

  • ПОЛУГРУППА — множество с одной бинарной операцией, удовлетворяющей закону ассоциативности. Понятие П. есть обобщение понятия группы:из аксиом группы остается лишь одна ассоциативность; этим объясняется и термин П. . П. называют иногда моноидами, но последний… …   Математическая энциклопедия

  • Алгебра — У этого термина существуют и другие значения, см. Алгебра (значения). Алгебра (от араб. الجبر‎‎, «аль джабр»  восполнение[1])  раздел математики, который можно грубо охарактеризовать как обобщение и расширение арифметики. Слово… …   Википедия

  • Дискретная математика — Дискретная математика  область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях. К числу таких структур могут быть отнесены конечные группы, конечные графы, а… …   Википедия

  • АЛГЕБРА — часть математики, посвященная изучению алгебраических операций. Исторический очерк. Простейшие алгебраич. операции арифметич. действия над натуральными и положительными рациональными числами встречаются в самых ранних математич. текстах,… …   Математическая энциклопедия

  • Список академических дисциплин — Эта статья содержит незавершённый перевод с иностранного языка. Вы можете помочь проекту, переведя её до конца. Если вы знаете, на каком языке написан фрагмент, укажите его в этом шаблоне …   Википедия

  • Полугруппа —         одно из основных понятий современной алгебры. П. называется множество с определённой на нём операцией, подчинённой закону ассоциативности (См. Ассоциативность). Понятие П. есть обобщение понятия группы (См. Группа): из аксиом группы… …   Большая советская энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»