Математическая энциклопедия » Что такое «Автоматов Алгебраическая Теория»?

Значение слова, определение и толкование термина

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

Avtomatov Algebraicheskaya Teoriya

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

С алгебраич. точки зрения, автомат (конечный или бесконечный) [Автоматов Алгебраическая Теория. Фото 1] является трехосновной алгеброй, т. е. алгеброй с тремя множествами [Автоматов Алгебраическая Теория. Фото 2] элементов и двумя операциями [Автоматов Алгебраическая Теория. Фото 3]: [Автоматов Алгебраическая Теория. Фото 4]X [Автоматов Алгебраическая Теория. Фото 5] С другой стороны, переходную систему [Автоматов Алгебраическая Теория. Фото 6] где [Автоматов Алгебраическая Теория. Фото 7]- входной алфавит, [Автоматов Алгебраическая Теория. Фото 8] - множество состояний (см. Автомат конечный), можно рассматривать как алгебру [Автоматов Алгебраическая Теория. Фото 9] с унарными операциями, обозначаемыми буквами а i входного алфавита Аи такими, что [Автоматов Алгебраическая Теория. Фото 10] Таким образом, для автоматов естественно определяются такие понятия, как автоматов гомоморфизм, изоморфизм, подавтомат и т. д. Вместе с тем этот подход позволяет сопоставить автомату [Автоматов Алгебраическая Теория. Фото 11] полугруппу преобразований множества S с операцией суперпозиции, порожденную операциями а i , так что для произвольных [Автоматов Алгебраическая Теория. Фото 12] из Аи s из S положено

[Автоматов Алгебраическая Теория. Фото 13]

Эта полугруппа наз. полугруппой автомата [Автоматов Алгебраическая Теория. Фото 14] она используется как средство описания определенных свойств автоматов (классификация, разложимость, изоморфизм и т. д.) на алгебраич. языке. В то же время всякой полугруппе Qс единицей можно сопоставить автомат с заданным входным алфавитом [Автоматов Алгебраическая Теория. Фото 15][Автоматов Алгебраическая Теория. Фото 16] и множеством состояний Qследующим образом. Каждой букве [Автоматов Алгебраическая Теория. Фото 17] из Аставят в соответствие нек-рый элемент [Автоматов Алгебраическая Теория. Фото 18] и тогда функцию переходов [Автоматов Алгебраическая Теория. Фото 19] можно определить так: [Автоматов Алгебраическая Теория. Фото 20] Полугруппа такого автомата изоморфна подполугруппе полугруппы [Автоматов Алгебраическая Теория. Фото 21] порожденной элементами [Автоматов Алгебраическая Теория. Фото 22] и тем самым в случае, если [Автоматов Алгебраическая Теория. Фото 23] суть образующие полугруппы [Автоматов Алгебраическая Теория. Фото 24] полугруппа автомата изоморфна исходной полугруппе [Автоматов Алгебраическая Теория. Фото 25]. Полугруппа автомата очевидным образом изоморфна фак-торполугруппе входной полугруппы всех слов в алфавите [Автоматов Алгебраическая Теория. Фото 26] с операцией последовательного соединения слов (конкатенация) по конгруэнции

[Автоматов Алгебраическая Теория. Фото 27]

Для произвольного состояния [Автоматов Алгебраическая Теория. Фото 28] конгруэнция Rявляется максимальной подконгруэнцией отношения

[Автоматов Алгебраическая Теория. Фото 29]

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

Автомат [Автоматов Алгебраическая Теория. Фото 31] наз. линейным автоматом (л. а.), если A, S и В - линейные пространства над нек-рым полем Р,

[Автоматов Алгебраическая Теория. Фото 32]

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

[Автоматов Алгебраическая Теория. Фото 35]

  • ВКонтакте

  • Facebook

  • Мой мир@mail.ru

  • Twitter

  • Одноклассники

  • Google+

См. также

  • , смеси, горение к-рых сопровождается световыми, тепловыми, звуковыми, дымовыми и реактивными пиротехн. эффектами. Основа большинства П. с.

  • (НООССН2)2--С(ОН)СООН, бесцв. кристаллы, tпл 153,5 0С. Широко распространена в природе. Получают Л. к. из махорки и брожения углеводов (сахар, патока