Автоматні відображення

Автоматне відображення — це відображення, породжене абстрактними автоматами.

Умови автоматності відображення

Будь-яке автоматне відображення повинно задовольняти наступні чотири умови:

1. Автоматне відображення здійснює однозначне відображення (як правило, часткове) безлічі слів в деякому кінцевому алфавіті Х (вхідне алфавітне відображення) в безлічі слів в деякому кінцевому алфавіті Y (вихідне алфавітне відображення).
2. Область визначення автоматного відображення задовольняє умові повноти, тобто разом з будь-яким внутрішнім словом, також, містяться всі початкові відрізки цього слова. Порожнє слово завжди входить в область визначення відображення.
3. Автоматне відображення φ зберігає довжину слова. Будь-яке слово р вхідного алфавіту на якому відображення φ визначено, має ту ж довжину, що і його образ φ(р). Зокрема, порожнє слово перекладається відображенням φ в порожнє слово.
4. Автоматне відображення φ переводить будь-який початковий відрізок слова р, на якому воно визначене, у відповідний (що має ту ж довжину) початковий відрізок слова φ(р).

Всі слова вхідного алфавіту розбиваються автоматним відображенням на два класи: на клас допустимих і клас заборонених слів. Сукупність усіх заборонених слів для даного автоматного відображення буде називатися його областю заборони.

Побудова автомата Мура

Розглянемо довільне (часткове) відображення φ, для якого виконуються сформульовані вище умови. Побудуємо абстрактний (частковий) автомат Мура U, станами якого будуть служити всілякі допустимі для відображення φ слова вхідного алфавіту Х = (х1, …, хn). Позначимо безліч всіх таких слів через А і визначимо функцію переходів φ(а, х) цього автомата таким чином: якщо aj — будь-яке слово з А, а XI — довільна буква вхідного алфавіту, то будемо вважати, що φ(aj, XI) дорівнює слову aj XI (виходить в результаті приписування букви XI до слова aj), якщо слово aj XI міститься в А, і що φ(aj, XI) НЕ визначена в іншому випадку.

Вибираючи як вихідний алфавіт автомата U вихідний алфавіт відображення φ, побудуємо зрушену функцію виходів U(а) автомата Мура U наступним чином: для будь-якого непорожньої слова аi з А вважаємо U(АІ) рівним останній букві слова φ(АІ); на порожньому слові функція U(а) залишається невизначеною.

Приклад

Як початковий стан автомата вибираємо пусте слово А і отримаємо автомат Мура, індукуючий вихідне відображення φ. Справді, нехай, q = xi1, xi2, …, xik — будь-яке допустиме слово відображення φ. Тоді всі його початкові відрізки будуть також допустимими словами (в силу умови 2). Після подачі на вхід побудованого автомата слова q, здійснюватиметься послідовний його переведення у стан U(q) = xi1, xi2, …, xik.

При цьому автомат видає деяку послідовність вихідних букв yj1, yj2, …, yjk = р. Зі способу визначення даного автомата випливає, що остання буква слова р збігається з останньою буквою слова φ(q), передостання буква слова р — з останньою буквою слова φ(xi1, xi2, …, xik- 1), яка в силу умови 4, збігається з передостанньою буквою слова φ(q) і т. д. Продовжуючи порівняння і використовуючи умови 3, можна встановити збіг всіх літер слова р з відповідними їм літерами слова φ(q). Отже, побудований автомат Мура U індукує вихідне (часткове) відображення φ.

Зв'язок автомату Мілі з автоматом Мура

Якщо алфавітне відображення φ задовольняє сформульованим вище чьотирьом умовам автоматності, то можна побудувати автомати Мілі та Мура (як правило, нескінченні), що індукують це відображення. У разі, коли область визначення відображення φ кінцева, ці автомати також можна вважати кінцевими.

Дана пропозиція дозволяє застосовувати терміни «автоматне відображення» по всьому алфавітниму відображенню, що задовольняє умовам автоматності.

З цієї пропозиції випливає конструктивний прийом, що дозволяє для будь-якого автоматного відображенню з кінцевою областю визначення (заданому на кінцевій множині слів) будувати індукующий це відображення кінцевий автомат Мілі або Мура.

Раніше розглядалася можливість інтерпретації автомата Мура як автомата Милі з тим же самим числом станів.

Теорема про зв'язок автомата Мілі і Мура

Для будь-якого кінцевого автомата Мілі існує еквівалентний йому (індукуючий те ж саме відображення) кінцевий автомат Мура. Існує єдиний конструктивний прийом (універсальний алгоритм перетворення автоматів Мілі в автомати Мура), що дозволяє за довільним кінцевим автоматом Мілі, що має m вхідних сигналів і n станів, побудувати еквівалентний йому автомат Мура, який має не більше m⋅n+1 станів.

Висновок

Умови автоматності накладають вельми жорсткі обмеження на клас відображень, які можуть бути індуковані абстрактними автоматами. Більшість алфавітних відображень, з якими доводиться мати справу на практиці, а саме більшість алгоритмів, не задовільняють ці умови. Однак існує стандартний прийом, що дозволяє індукувати будь-яке алфавітне відображення в автоматне.

Див. також

• Автомат Мура
• Автомат Мілі
• Теорія автоматів
• Абстрактна теорія автоматів

Джерела

1. Карел Чулик Конструкция автоматного отображения [ 29 травня 2014 у Wayback Machine.]
2. Бабаш А. В., Глухов М. М., Шанкин Г. П. «О преобразованиях множества слоев в конечном алфавите, не размножающих искажений», Дискретная математика, 9:3 (1997), 3–19
3. Глухов М. М. «Инъективные отображения слов, не размножающие искажений», Труды по дискретной математике, 4 (2001), 17–32.