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

Для будь-якого автомата Мілі можна побудувати відповідний автомат Мура, і навпаки.

Розглянемо алгоритми таких переходів на прикладі автомата Мура, що заданий табл. 5.7 і табл. 5.8.

Таблиця 5.7.	Таблиця 5.8.
Таблиця 5.9.

Поставимо у відповідність кожній парі Q_m та X_p автомата Мілі стан Q_mp автомата Мура. До множини станів автомата Мура включимо початковий стан автомата Мілі , але позначимо його . Для прикладу, що розглядається, така відповідність приведена в табл. 5.9.

Якщо автомат Мілі має m станів і p вхідних сигналів, то відповідний йому автомат Мура матиме станів.

З табл. 5.9 витікає той факт, що стан автомата Мілі співпадає зі станами , , , , автомата Мура. Тобто має місце наступна тотожність:

.

Аналогічно,

; ; .

Така відповідність означає, що одному переходу автомата Мілі з Q₀ в Q₁ повинні бути відповідними всі переходи автомата Мура зі станів Q₀₀ , Q₂₁ , Q₁₂ , , в стан ; переходу з в повинні бути відповідні всі переходи автомата Мура зі стану в стани , , , , і т.д. Зі сказаного витікає наступний висновок: якщо стан Q_mp входить до множини станів, що співпадає зі станом, наприклад, Q₁ , то стовбець таблиці переходів для стану Q_mp співпадатиме з стовбцем таблиці переходів для стану Q₁ . Значення m функції виходів для еквівалентного автомата Мура:

при .

Наприклад, для стану Q₀₁ функція виходу буде Y₃ , оскільки вона відповідає набору Q₀ і X₁ з тбл. 5.8; для стану Q₀₂ функція виходу буде Y₂ , що відповідає набору Q₀ і X₂ , і т. д.

Для початкового стану Q₀₀ значення вихідного сигналу вибирається довільно.

Внаслідок описаних відповідностей і перетворень можна побудувати таблицю переходів і виходів еквівалентного автомата Мура (див. табл. 5.10).

Таблиця 5.10.

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

Якщо і функції переходів і виходів автомата Мура, то функції переходів і виходів еквівалентного автомата Мілі:

; .

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

При такому перетворенні граф автомата Мілі відрізняється від графу автомата Мура лише тим, що вихідні сигнали з вузлів графа перенесені на всі гілки, що входять у даний вузол.