Еквівалентні перетворення автоматів

Визначення 1. Два автомати А і А , у яких співпадають як вхідні, так і вихідні алфавіти, називаються еквівалентними, якщо для будь-якого вхідного слова, що поступає одночасно на входи автоматів А і А , попередньо встановлених в початковий стан, вихідні слова цих автоматів співпадатимуть.

Поставимо у відповідність кожному стану автомата Милі стан автомата Мура, де ; .

В результаті одержимо взаємнооднозначні відповідності між станами і b автоматів Милі і Мура - в які введемо також і відповідність між їх початковими станами а і b . Тоді загальна кількість відповідностей дорівнює

Теорема. Для кожного автомата Милі існує еквівалентний йому автомат Мура.

Доказ. Оскільки кожному стану автомата Милі відповідає вихідна буква у , α = 1,2...k, до, то через відповідність ця ж буква у буде відповідати стану b автомата Мура. В результаті на виходах автоматів Милі і Мура за наявності одних і тих же букв на їх входах з'являтимуться однакові вихідні букви, і, отже, ці автомати будуть еквівалентні. Теорема доведена.

Розглянемо алгоритм побудови автомата Мура на основі автомата Милі.

Припустимо, що під впливом вхідних сигналів а і x у момент часу t на виході автомата Милі було одержано стан , а у момент часу t+1 поступила нова буква x . Тоді автомат Милі перейде із стану в стан

Так як , то відповідно автомат Мура в цьому випадку повинен перейти із стану в стан ~ а .

Отже, для визначення стану b автомата Мура треба спочатку знайти стан автомата Милі, який знаходиться в клітинці на перетині а - ї колонки і x - го рядка таблиці переходів автомата Милі.

Одночасно з цим визначається стан b автомата Мура.

Знаючи стан , по таблиці переходів автомата Милі визначається його стан , в який він перейде під час вступу сигналу x , і потім по цьому стану знаходиться відповідний йому новий стан , в який перейде автомат Мура під дією сигналу x .

В результаті буде отримано стан автомата Мура, в який він перейде із стану b під впливом вхідного сигналу x .

Таким чином заповнюються всі стовпців таблиці переходів автомата Мура для всіх початкових букв (x , x ,…, x ).

По таблиці виходів автомата Милі для кожного стану і відповідно b знаходиться вхідний сигнал у , який проставляється вгорі відповідних стовпців таблиці переходів автомата Мура. Вона тепер називатиметься таблицею переходів-виходів автомата Мура.

Приклад 1 Дані таблиці 1, 2 переходів і виходів автомата Милі. Вимагається побудувати таблицю переходів-виходів автомата Мура.

Таблиця 1 – Переходи автомата Мил

Таблиця 2 – Виходи автомата Милі

Алгоритм рішення цієї задачі полягає в наступному.

1. На основі табл. 1, 2 будується суміщена таблиця 3 переходів автоматів Мілі-Мура. Для цього в кожну клітину таблиці переходів автомата Милі, що знаходиться на перетині а -го стану і х -го вхідного сигналу, до стану , дописується стан . В клітинку з початковим станом а ₀ автомата Милі дописується початковий стан b₀ автомата Мура.

Таблиця 3 – Суміщена таблиця переходів автоматів Мілі-Мура

 

2. З таблиці 3 виписуються послідовно по рядках, відповідним змінним (x , x , …, x ), стани b автомата Мура, починаючи з b , які заносяться в таблицю 4 переходів - виходів автомата Мура в рядок «Стан». В результаті цей рядок міститиме станів , де - алфавіт станів автомата Мура.

Таблиця 4 – Переходи-виходи автомата Мура

3. Для заповнення клітинок в табл.. 4 автомата Мура, які знаходяться на перетині змінних з станами , в які записуються його стани , необхідно спочатку по табл..3 відповідні стану автомата Мура стани автомата Мілі. Знаючи стан і змінну , по тій же табл..3 находять стан автомата Мура, в який він переходить із стану під впливом вхідного сигналу .

В клітину, що знаходиться на перетині стовпця таблиці 4 і рядка, який відповідає букві ставиться значення стану автомата Мура. Аналогічним чином заповнюється решта клітин таблиці 4.

 

4. По таблиці 2 визначаються вихідні сигнали автомата Милі, яким ставляться у відповідність стани в суміщеній таблиці 3 переходів автоматів Мілі-Мура. Ці сигнали потім проставляються у відповідних стовпцях таблиці 4 переходів-виходів автомата Мура, створюючи таким чином рядок «Вихідний сигнал». В результаті буде закінчено побудову таблиці 4 переходів-виходів автомата Мура.

Визначимо, наприклад, по табл.3 стан, в який повинен переходити автомат Мура, що знаходиться в стані (див.табл.4), при подачі на його вхід сигналу . Стану відповідає пара символів . Автомат Милі при цьому, відповідно з табл.3, знаходиться в стані . На перетині рядка і стовпця табл.3 знаходимо стан автомата Мура.

Знаючи стан і , по табл.2 виходів автомата Милі, легко визначається вихід автомата Мура, який відповідає стану .

Аналогічно визначаються переходи і для решти станів автомата Мура при дії вхідного сигналу або .

На рис.3 теми «Форми задання цифрових автоматів» отримані всі стани автомата Мура, відповідні автомату Милі для продажу газет.