Перетворення автомата Мура в автомат Мілі

Побудова автомата Мілі виконується на підставі запізнення реакції автомата Мура у порівнянні з автоматом Мілі.

Нехай заданий автомат Мура А_A = (S_A, X_A, Y_A, d_A, l_A, {s_0A}), еквівалентний йому автомат Мілі А_B = (S_B, X_B, Y_B, d_B, l_B, {s_0B}) будується в такий спосіб:

S_B : = S_A,

X_B : = X_A,

Y_B : = Y_A,

d_B : = d_A,

s _0B: = s _0A.

l_B будується в такий спосіб, якщо в автоматі Мура d(s_і,, x_j) = s_h і l_A(s_h) = y_m, то в автоматі Мілі l_B(s _і, x_j) = y_m.

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

При табличному способі завдання автоматів таблиця виходів еквівалентного автомата Мілі виходить з таблиці переходів вихідного автомата Мура заміною символу s_h, що стоіть на перетинанні рядка x_j і стовпця s_i, символом вихідного сигналу y_m, що відрізняє стовпець s_h у таблиці переходів автомата Мура.

Приклад. Вихідний автомат Мура (рис.19.2 ліворуч) і еквівалентний йому автомат Мілі (рис. 19.2 праворуч). Виконано перенос вихідних сигналів з вершин на вхідні в них дуги.

Рис. 19.2. Автомат Мура й еквівалентний йому автомат Мілі