ПЕРЕТВОРЕННЯ МІЛІ – МУР

3. Перетворення автомата Мура у еквівалентний автомат Мілі

Перехід від автомата Мура до еквівалентного йому автомата Мілі тривіальний і легко здійснюється при графічному способі завдання автомата. Для здобуття графа автомата Мілі необхідно вихідний сигнал y_g, що викликаний станом q_s автомата Мура, перенести на всі дуги, що входять в цю вершину. На малюнках приведені граф автомата Мілі та еквівалентного автомату Мура:

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

4. Перетворення автомата Мілі у еквівалентний автомат Мура

Перехід від автомата Милі до еквівалентного йому автомата Мура складніший. Це пов'язано з тим, що в автоматі Мура в кожному стані виробляється лише один вихідний сигнал. Наведений нижче спосіб передбачає, що до кожного стану можна перейти з інших, принаймні з одного. Як і у попередньому випадку, перехід найбільш наочно робити при графічному способі завдання автомата. В цьому випадку кожен стан q_i початкового автомата Мілі породжує стільки станів автомата Мура, скільки різних вихідних сигналів виробляється в початковому автоматі при попаданні в стан q_i.

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

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

Я к випливає зі схеми автомата Мілі при переході автомата у стан q₁ виробляються вихідні сигнали y₁ або у₂, при переході у q₂ – y₂ або у₃, q₃ – y₁ або у₃, q₀ – y₃. Кожній парі станів q_i - вихідний сигнал yj, який генерується при переході у цей стан, поставимо у відповідність стан q_ik еквівалентного автомата Мура з тим же вихідним сигналом y_j : q₁₁ = (q₁, y₁), q₁₂ = (q₁, y₂), q₂₁ = (q₂, y₂), q₂₂ = (q₂, y₃), q₃₂ = (q₃, y₁), q₃₁ = (q₃, y₃), q₀ = (q₀, y₃), тобто кожен стан q_i автомата Мілі породжує деяку множину Q_i станів еквівалентного автомата Мура: Q₁ = { q₁₁, q_­12}, Q₂ = { q₂₁, q₂₂ }, Q₃ = { q_31, q₃₂ }, Q₀ = { q₀ }. Як видно, в еквівалентному автоматі Мура кількість станів 7. Для побудови графа автомата Мура поступаємо таким чином. Оскільки у автоматі Мілі є перехід зі стану q₀ у стан q₁ під дією сигналу x₁ з видачею y₁, то із множини станів Q₁ = { q₁₁, q_­12}, породжуваних станом q₁ автомата Мілі в автоматі Мура має бути перехід в стан (q₁, y₁) = q₁₁ під дією сигналу x₁ і т.д. Граф еквівалентного автомата Мура представлений на мал.

Якщо від автомата Мура S_b, еквівалентного автомату Мілі (мал. ), знову перейти до автомату Мілі, то отримаємо автомат Мілі

Унаслідок транзитивності відношення еквівалентності два автомати Мілі також будуть еквівалентними, але в останнього будуть на 3 стани більше. Тому що еквівалентні між собою автомати можуть мати різне число станів, у зв'язку з чим виникає задача знаходження мінімального (тобто з мінімальним числом станів) автомата в класі еквівалентних між собою автоматів.