ад ним і вивчення їх властивостей. p> Узагальнюючи вище сказане, хотілося б сказати, що теорія представлень груп дозволила по-новому зрозуміти класичні результати теорії автоморфних функцій, ширше поставити завдання цієї теорії і отримати ряд нових важливих результатів.
5.4 Алгебраїчні конструкції в теорії автоматів
Теорія автоматів оперує з широким колом алгебраїчних об'єктів і засобів. У роки становлення теорії автоматів алгебраїчні засоби активно використовувалися для вирішення її внутрішньої проблематики. Цікаво, що з часом виявилося, методи теорії автоматів можна використовувати при алгебраїчних дослідженнях. p> Першої систематичною роботою, в якій розкрилася повною мірою зв'язок між двома цими областями, була робота Глушкова.
Особливе місце в теорії автоматів займають алгебраїчні конструкції, пов'язані з кінцевими напівгрупами. Розглянемо це питання більш докладно на простому прикладі. p> Нехай є автомат
В
Де і, вхідний і вихідний алфавіти відповідно, - безліч станів, функція - функція виходів. З цим кінцевим автоматом можна пов'язати напівгрупу підстановок на множині. Кожна буква вхідного алфавіту діє на Q як підстановка, причому. Послідовне дію букв і відповідає добутку підстановок Для виконується
Таким чином, безліч породжує кінцеву напівгрупу, звану внутрішньої полугруппой автомата Очевидно є гомоморфним чином вільної напівгрупи А * (А * - безліч всіх слів в алфавіті).
Отже, ми побачили, що напівгрупи виникають фактично відразу ж при визначенні поняття В«автоматВ».
Методи теорії напівгруп в цій області можна, взагалі кажучи, багато де застосувати. Наприклад, методи теорії кінцевих напівгруп можна використовувати для вирішення важливої вЂ‹вЂ‹задачі декомпозиції автоматів, тобто подання автомата у вигляді з'єднання В«простихВ» автоматів. Виявилося, що ці методи добре працюють в тому випадку, коли автомат можна розкласти в суперпозицію автоматів. Серед робіт у цьому напрямку одне з центральних місць займає робота 60-х років Крона і Роудз. У цій роботі показано, як внутрішня півгрупа автомата суперпозиції пов'язана з внутрішніми напівгрупами автоматів - компонентів з'єднання. p> Як ми побачили, з кожним автоматом можна пов'язати напівгрупу. Справедливо і зворотне слідство. Кожній абстрактної полугруппе можна поставити у відповідність автомат. Правда це буде не один автомат, а нескінченна безліч автоматів. p> Ще відзначимо, що теорія напівгруп застосовується для вирішення центральної задачі теорії автоматів - завдання про виразність.
Також варто сказати, що не тільки кінцеві напівгрупи застосовуються при вирішенні завдань з теорії автоматів. Тут знайшли своє застосування і нескінченні групи. p> Отже, теорія автоматів активно використовує класичні об'єкти з алгебри, а також вводить в розгляд нові алгебраїчні системи і надає нові В«некласичніВ» конструкції.
5.5 Проблема інтегрування д...
