Автоматні відображення
Автоматне відображення — це відображення, породжене абстрактними автоматами.
Умови автоматності відображення[ред. | ред. код]
Будь-яке автоматне відображення повинно задовольняти наступні чотири умови:
- Автоматне відображення здійснює однозначне відображення (як правило, часткове) безлічі слів в деякому кінцевому алфавіті Х (вхідне алфавітне відображення) в безлічі слів в деякому кінцевому алфавіті Y (вихідне алфавітне відображення).
- Область визначення автоматного відображення задовольняє умові повноти, тобто разом з будь-яким внутрішнім словом, також, містяться всі початкові відрізки цього слова. Порожнє слово завжди входить в область визначення відображення.
- Автоматне відображення φ зберігає довжину слова. Будь-яке слово р вхідного алфавіту на якому відображення φ визначено, має ту ж довжину, що і його образ φ(р). Зокрема, порожнє слово перекладається відображенням φ в порожнє слово.
- Автоматне відображення φ переводить будь-який початковий відрізок слова р, на якому воно визначене, у відповідний (що має ту ж довжину) початковий відрізок слова φ(р).
Всі слова вхідного алфавіту розбиваються автоматним відображенням на два класи: на клас допустимих і клас заборонених слів. Сукупність усіх заборонених слів для даного автоматного відображення буде називатися його областю заборони.
Побудова автомата Мура[ред. | ред. код]
Розглянемо довільне (часткове) відображення φ, для якого виконуються сформульовані вище умови. Побудуємо абстрактний (частковий) автомат Мура 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 станів.
Висновок[ред. | ред. код]
Умови автоматності накладають вельми жорсткі обмеження на клас відображень, які можуть бути індуковані абстрактними автоматами. Більшість алфавітних відображень, з якими доводиться мати справу на практиці, а саме більшість алгоритмів, не задовільняють ці умови. Однак існує стандартний прийом, що дозволяє індукувати будь-яке алфавітне відображення в автоматне.
Див. також[ред. | ред. код]
Джерела[ред. | ред. код]
- Карел Чулик Конструкция автоматного отображения [Архівовано 29 травня 2014 у Wayback Machine.]
- Бабаш А. В., Глухов М. М., Шанкин Г. П. «О преобразованиях множества слоев в конечном алфавите, не размножающих искажений», Дискретная математика, 9:3 (1997), 3–19
- Глухов М. М. «Инъективные отображения слов, не размножающие искажений», Труды по дискретной математике, 4 (2001), 17–32.