Безліч П із заданою в ньому бінарної асоціативної операцією називається полугруппой. Напівгрупа з одиничним елементом називається моноїд (або просто полугруппой з одиницею).
1. Нехай X - довільна множина, М (Х)-безліч всіх відображень X в себе. Тоді щодо операції композиції відображень М (X) - моноїд, він некомутативними. Позначимо його М (Х, О. ех).
2. Безліч квадратних матриць порядку п щодо множення матриць - некомутативними моноїд з одиничним елементом - одиничною матрицею, а щодо складання матриць - комутативними моноїд з одиничним елементом - нульовий матрицею. Позначимо їх відповідно (Mn (R), •, E), (Mn (R), +, 0).
3. Безліч цілих чисел - комутативними моноїд як щодо складання, так і множення. Позначимо їх відповідно (Z. +, 0), (Z. •, 1). Безліч цілих чисел, що діляться на n (n> 1), - комутативна півгрупа без одиниці щодо множення. Позначимо її (nZ, •).
4. Нехай A = a1. аn> - кінцеве безліч символів - алфавіт. Кінцева послідовність символів називається словом в алфавіті А. На безлічі П слів в алфавіті А введемо бінарну операцію- «приписування», тобто якщо то . Тоді П - півгрупа. Вона називається вільної полугруппой, породженої безліччю А.
5. Безліч X1, X2. Х3. Х4> щодо операції, заданої таблицею Келі (див. Табл. 8.1.), - комутативними моноїд, одиничний елемент якого Х1.
Підмножина П 'напівгрупи П називається подполугруппой, якщо аbЄП' для всіх а, bЄП '. В цьому випадку говорять також, що підмножина П 'замкнуто щодо даної операції. Очевидно, подполугруппа П 'сама є полугруппой щодо операції в П. Якщо М - моноїд і підмножина М' не тільки замкнуто щодо операції, але і містить одиничний елемент, то М 'називається подмоноідом М.
Наприклад, безліч чисел, кратних п, - подполугруппа в полугруппе цілих чисел щодо множення (Z. •, 1) і подмоноід в (Z. +, 0). У полугруппе П слів в алфавіті А підмножина слів в алфавіті А # 900; А також подполугруппа.
Елемент а моноїд М з одиничним елементом е називається оборотним, якщо для деякого елемента b виконується рівність ab = ba = e. Елемент b називається зворотним а й позначається a-1. Зворотний елемент єдиний. Дійсно, якщо ще і ab '= b'a = e, то b' = eb # 900; = (ba) b '= b (ab') = be = b.
Безліч всіх оборотних елементів моноїд утворює подмоноід, так як містить одиничний елемент і замкнуто щодо операції: якщо а і b оборотні, то b-la-1 - елемент, зворотний ab.
Розглянемо проблему тотожності слів в напівгрупах.
Нехай S = s1, .sn> - підмножина елементів напівгрупи П таке, що будь-який елемент з П може бути представлений як добуток елементів з S. Тоді безліч S називається системою утворюючих напівгрупи П. Наприклад, для вільної напівгрупи П, породженої алфавітом A = a1 ,. аn>, саме безліч А є системою утворюють; для напівгрупи цілих чисел щодо складання (Z. +, 0) системою утворюючих є безліч, а для напівгрупи цілих чисел щодо множення (Z. •, 1) утворюють є все прості числа і одиниця.
Слід зауважити, що далеко не всі твори елементів безлічі S будуть різними елементами напівгрупи П. В загальному випадку питання про рівність таких творів довольносложен.
Будемо розглядати напівгрупи, породжені кінцевим безліччю своїх елементів. Вони називаються звичайно-породженими.
Можна вказати деякий спосіб завдання напівгруп без використання індивідуальних властивостей елементів безлічі, в якому визначена полугрупповая операція, а саме завдання напівгрупи утворюють і визначальними співвідношеннями.
Кожна півгрупа П може бути задана утворюють
(Алфавіт напівгрупи) і визначальними співвідношеннями
Елемент напівгрупи, тобто слово в алфавіті (8.2.1), називають словом напівгрупи П.
Елементарним перетворенням напівгрупи П називається перехід від слова виду XAi Y до слова XBi Y (або назад), де X, Y. - довільні слова напівгрупи П, а Ai = Bi; - одне з визначальних співвідношень (8.2.2).
Елементарні перетворення представляються у вигляді схем
До схем елементарних перетворень відносяться також тавтологічні переходи виду Х → Х. Графічне збіг двох слів X і Y позначають Х # 333; Y.
Співвідношення (8.2.2.) Визначають рівність слів в полугруппе П, яке пов'язане з елементарними перетвореннями напівгрупи П наступним чином. Два слова X і Y напівгрупи П рівні в П тоді і тільки тоді, коли можна вказати послідовність елементарних перетворень напівгрупи П
переводить слово X в слово У.
Для вільної напівгрупи з алфавітом (8.2.1.) Безліч визначальних співвідношень порожньо; два слова рівні тоді і тільки тоді, коли вони графічно збігаються.
Напівгрупу (Z. +, 0) цілих чисел щодо складання можна задати утворюють і визначальними (в адитивної записи) співвідношеннями:
Проблема тотожності слів в полугруппе полягає в наступному: вказати алгоритм, який за будь-якими двома словами встановлював би, рівні вони в полугруппе П чи ні. Доведено, що ця проблема алгоритмічно нерозв'язна. Простим прикладом напівгрупи з нерозв'язною проблемою тотожності слів є півгрупа зутворюють а, b, с, d, e і визначальними співвідношеннями ас = са, ad = da. bс = сb, bd = db. єса = CЕ, edb = de. сса = ссае.