Комбинаторное приложение теории полугрупп. Языки коды автоматы

Языки и полугруппы

Понятие преобразования принадлежит к числу самых важных математических понятий. Примечательно, что множество T (X ) является полугруппой относительно операции умножения (называемой также композицией или суперпозицией), определяемой следующим образом: произведением преобразований f и g называется преобразование f g, заданное условием
f g(x) = f (g(x))
для любого x k X. Другими словами, f g есть результат последовательного выполнения сначала преобразования g, затем преобразования f. Легко убедиться в ассоциативности этого умножения. Полугруппу T (X ) называют полной полугруппой преобразований (или симметрической полугруппой) на множестве X.
Кроме T (X ) можно указать различные другие естественные полугруппы относительно композиции, состоящие из преобразований множества X, где X - либо произвольное множество, либо множество, наделенное какой-либо математической структурой: алгебраической, геометрической, топологической и т.п. Таковы, например, группа всех взаимно однозначных отображений произвольного множества X на себя (называемая симметрической группой на множестве X - это один из важнейших примеров групп), многочисленные полугруппы операторов - для случая, когда X есть какое-либо из пространств, изучаемых в функциональном анализе, и многие-многие другие полугруппы преобразований. Все такие полугруппы являются подполугруппами соответствующей полной полугруппы преобразований. О понятии подполугруппы немного поговорим в конце раздела 1.
Пусть X - произвольное множество, а Y - одно из числовых множеств N, Z, Q, R. Через T (X, Y ) обозначим множество всех отображений (функций) из X в Y. На множестве T (X, Y ) можно определить операцию + (так называемое поточечное умножение функций), сопоставляя любым двум функциям их произведение f + g, заданное следующим условием: для любого x k X
f + g(x) = f (x)g(x),
где в правой части равенства осуществляется обычное умножение чисел в Y. Легко видеть, что такое умножение функций ассоциативно - имеем еще одно семейство полугрупп.
Пусть A - произвольное (непустое) множество. Будем здесь называть A алфавитом, а элементы A - буквами. Через FA обозначим множество всех конечных последовательностей букв из A. Зададим на FA операцию умножения, полагая
(a1 , _, am) " (b1 , _, bn) = (a1 , _, am , b1, _, bn).
Легко видеть, что эта операция (называемая иногда конкатенацией, то есть сцеплением) ассоциативна, так что FA становится полугруппой, которая называется свободной полугруппой над алфавитом A. Другое употребительное обозначение для нее - A +.
Отождествляя последовательность из одной буквы с самой этой буквой и опуская в записи точку для конкатенации, получаем (a1 , a2 , _, am) = a1a2_am . В виде таких произведений, как правило, и записывают элементы свободной полугруппы и называют их словами. По определению, слова a1a2_am и c1c2_ck равны, если m = k и ai = ci при i = 1, _, m.
Свободные полугруппы наряду с симметрическими играют важную роль как в общей теории полугрупп, так и в приложениях. Их прикладная роль объясняется, в частности, тем, что во многих процессах передачи информации передаваемые сообщения представляют собой цепочки символов ("реальных" букв или слов, других кодовых знаков, электрических сигналов и т.д.) и соединение двух таких цепочек есть не что иное, как конкатенация слов в подходящей свободной полугруппе. Свободные полугруппы (главным образом над конечными алфавитами) явля