Математическая энциклопедия




Математическая энциклопедия
АВТОМАТОВ АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ -
АВТОМАТОВ АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ

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

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


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


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


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

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


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



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

ПОЛИГОН ПОЛИГОН над моноидом R, R -полигон, операнд,- непустое множество с моноидом операторов. Точнее, непустое множество Аназ. левым П. над моноидом К, если для любых и определено произведение , причем и 1а=а для любых . Правый П. определяется аналогично. Задание R-полигона Аравносильно з
АВТОМАТ АВТОМАТ - управляющая система, являющаяся автоматом конечным или некоторой его модификацией, полученной путем изменения компонент или функционирования. Основное понятие - конечный А. - возникло в середине 20 в. в связи с попытками описать на математическом языке функционирование нервных
АВТОМАТА ПОВЕДЕНИЕ АВТОМАТА ПОВЕДЕНИЕ - математическое понятие, описывающее взаимодействие автомата с внешней средой. Так, для автомата конечного внешней средой обычно является множество входных слов, а поведением - словарная функция, реализуемая автоматом, или событие (иногда сверхсобытие), представимое автоматом.
ПОЛУГРУППА ПОЛУГРУППА - множество с одной бинарной операцией, удовлетворяющей закону ассоциативности. Понятие П. есть обобщение понятия группы:из аксиом группы остается лишь одна - ассоциативность; этим объясняется и термин "П.". П. называют иногда моноидами, но последний термин употребляется чаще
АЛГЕБРА АЛГЕБРА - часть математики, посвященная изучению алгебраических операций. Исторический очерк. Простейшие алгебраич. операции - арифметич. действия над натуральными и положительными рациональными числами - встречаются в самых ранних математич. текстах, свидетельствующих о том, что уже в гл

Заказать работу



наверх страницынаверх страницы на верх страницы





© Библиотека учебной и научной литературы, 2012-2016 Рейтинг@Mail.ru Яндекс цитирования