Пояснення

Кожен стан 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₁ і т.д. Граф еквівалентного автомата Мура представлений на другому рисунку (зправа).

Дата добавления: 2015-07-21