Розділ 2. Загальна методика обчислень
§ 2.1. Допоміжні конструкції
В цьому підрозділі розглядається множина автоматів . На цій множині вводиться нумерація, відношення еквівалентності, яке зберігає напівгрупи, та описується клас автоматів, що мають одиничну функцію росту і породжують скінченні моногенні напівгрупи.
2.1.1. Нумерація автоматів Мілі
Якщо , , то існує різних функцій та різних функцій , а тому множина складається з автоматів.
Занумеруємо букви алфавіту числами від до , а стани множини - числами від до . Номер букви та стану позначимо символами та відповідно. Довільну функцію переходів задамо таблицею значень:
де , , . Пов'яжемо з функцією переходів номер , що визначається рівністю
Зрозуміло, що номер функції переходів лежить в межах від (коли для всіх , ) до
(якщо всі ). Крім того, функція переходів однозначно відновлюється за своїм номером .
Аналогічно, функції виходів присвоїмо номер за формулою:
де , , . При цьому лежить в межах від (коли для всіх , ) до
(якщо всі ). Надалі номери функцій переходів та виходів будемо позначати верхнім індексом в дужках. Остаточно, довільному автомату присвоїмо номер
Очевидно, що при цьому автомати множини нумеруються номерами від до .
Приклад. Нехай автомат . Так як
то його функції переходів і виходів мають таблиці значень:
, , , ;
, , , .
2.1.2. Еквівалентні автомати
Введемо таке відношення на множині автоматів Мілі .
Означення 2.15. [29] Два автомати Мілі , , будемо називати еквівалентними, якщо існують перестановка алфавіту та перестановка множини станів такі, що мають місце співвідношення:
та ,
для усіх та .
Це відношення є еквівалентністю на множині автоматів , бо автомати та еквівалентні тоді і тільки тоді, коли вони є ізоморфними (за озн. 1.2) для таких перестановок і , що . Зазначимо, що введене відношення еквівалентності зберігає оборотність автоматів. Покажемо, що еквівалентні автомати Мілі породжують ізоморфні напівгрупи перетворень і тому мають однакові функції росту.
Твердження 2.13. [29] Нехай - деякий автомат Мілі; та - довільні перестановки елементів множин та . Побудуємо автомат , що та для усіх і . Тоді напівгрупи, які породжуються автоматами і , ізоморфні, тобто .
Доведення. З умов випливає, що функції переходів та виходів автомату залежать від функцій переходів та виходів автомату таким чином:
Позначимо автоматні перетворення, які задаються автоматом , як , а перетворення, що задаються автоматом , як . Покажемо, що для довільного стану та довільного слова , , виконується співвідношення:
.Скористаємось індукцією за довжиною слова . База індукції - випадок . З маємо:
тобто виконується. Враховуючи індукційне припущення, для слова , , з маємо:
що і доводить . Очевидно, що автомат отримується з автомата за допомогою перестановок та , і тому:
.Таким чином, з та випливає, що відображення , задане рівністю , де для довільного покладемо , є ізоморфізмом напівгруп та . (
Використовуючи формулу для кількості класів попарно неізоморфних автоматів (тв. 1.1), неважко знайти кількість класів введеної в означенні 2.15 еквівалентності на множині , а саме,
Твердження 2.14. Максимальна кількість попарно нееквівалентних автоматів з множини дорівнює:
Зокрема, при та звідси отримуємо . Представником класу еквівалентності будемо вибирати автомат з найменшим номером в розумінні введеної вище нумерації .
2.1.3. Вироджені автомати
Розглянемо спеціальний клас автоматів з множини .
Означення 2.16. Автомат такий, що для довільної букви та будь-яких станів має місце рівність , тобто для всіх , будемо називати виродженим.
Твердження 2.15. Функція росту автомату Мілі в усіх точках дорівнює одиниці тоді і тільки тоді, коли він вироджений. При цьому напівгрупа є скінченною моногенною.
Доведення.
Необхідність. За умовою , тому автомат після мінімізації має єдиний стан. Це може бути тільки тоді, коли всі перетворення , , співпадають. Звідси для будь-якої і довільних випливає рівність
тобто перетворення та збігаються. За означенням, такий автомат є виродженим.
Достатність. За умовою твердження для всіх , і позначимо це перетворення . Для довільного слова і кожного перетворення , , виконується:
де . Тоді всі перетворення автомату збігаються над , і для існує рівносильний автомат з єдиним станом, функції переходів та виходів якого задаються таким чином:
де . Рівносильність автоматів та очевидна.
Оскільки функція росту автомату з одним станом в кожній точці дорівнює одиниці, то отримуємо твердження теореми. Далі, за побудовою
де , і тому є скінченною моногенною напівгрупою. (
Функція виходів виродженого автомата задається деяким перетворенням алфавіту . Тому вироджені автомати з множини мають різних функцій виходів, а на функції переходів ніяких обмежень не накладається. Таким чином, в множині існує вироджених автоматів.
Очевидно, що клас еквівалентності автоматів, який містить хоча б один вироджений автомат, складається лише з вироджених автоматів. З твердження 2.14 дістаємо формулу для числа класів еквівалентності, які складаються з вироджених автоматів.
Твердження 2.16. Кількість класів еквівалентності на множині , які повністю складаються з вироджених автоматів, дорівнює:
де
З твердження 2.15 випливає, що для дослідження напівгруп, які породжуються автоматами з , або при вивченні функцій росту самих автоматів достатньо розглянути невироджені попарно нееквівалентні автомати, кількість яких дорівнює . Множина містить класи еквівалентності, які складаються з вироджених автоматів, а отже в існує точно невироджених попарно нееквівалентних автомати.
§ 2.2. Обчислювальний комплекс
2.2.1. Загальний огляд
Об'єм обчислень у задачі табулювання функцій росту всіх автоматів із станами над -елементним алфавітом швидко зростає з ростом значень параметрів, бо згідно з твердженням 2.14 кільк
- Київ+380960830922