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

У теорії автоматів доведено, що кожному автомату Мілі можна поставити у відповідність еквівалентний автомат Мура, і навпаки.

Означення 4.5. Два автомата, що мають однакові вхідні і вихідні алфавіти, називаються еквівалентними, якщо вони, починаючи з одного і того ж початкового стану, на будь-які однакові вхідні послідовності відповідають однаковими вихідними послідовностями. При цьому число їх внутрішніх станів може бути різним.

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

Подання реального автомата абстрактною моделлю Мура чи Мілі є суто умовним і залежить від його функціонального призначення. Наприклад, дорожній автомат зручніше зображувати моделлю Мура, оскільки сигнал автомата, який керує світлофором, має діяти весь час, поки останній “горить” певним кольором (задає напрям руху). У цьому ви­падку керувальний (вихідний) сигнал автомата зручно ототожнювати з його станом, що й описує модель Мура. В інших автоматах, наприклад, коли період їх стійкості відповідає часу дії вхідних сигналів, а вихідний сигнал з’являється лише короткочасно і під час переходу між цими станами (наприклад, як у схемі десяткового лічильника), зручно користуватися моделлю у вигляді автомата Мілі. Отже, під “станом” розуміють не деяку істотну властивість автомата, а лише спосіб для опису минулого (передісторії) автомата, що дає змогу усунути час як явну змінну.

У зв‘язку з викладеним постає потреба переходити від автомата одного типу до еквівалентного автомата іншого типу.

Коли задано граф автомата Мура, то за ним можна перейти до графа еквівалентного автомата Мілі наступним чином: вихідний сигнал w_g, записаний по­руч з вершиною q_s, переносять на всі дуги, що входять в цю вершину (рис. 4.11). Під час такого перетворення функції переходів в автоматі А Мура і автоматі А' Мілі залишаються однаковими: і . Функції виходів: для автомата Мура , а для автомата Мілі .

Із самої побудови графа автомата Мілі можна побачити, що він еквівалентний автомату Мура. Справді, коли деякий вхідний сигнал x_f ÎX надійде на вхід автомата А, що перебуває в стані q_m, то він перейде в стан і видасть вихідний сигнал . Але відповідний автомат Мілі А' із стану q_m також пере­йде в стан q_s, оскільки d_А'(q_m,z_f)=d_А(q_m,z_f)=q_s, і видасть той самий вихідний сигнал згідно зi способом побудови функції λ_А.

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