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

Нехай заданий автомат Мілі A_А = (S_А, X_А, Y_А, d_А, l_А, {s_0А}). Еквівалентний йому автомат Мура A_В = (S_В, X_В, Y_В, d_У, l_У, {s_0В }) будується в такий спосіб:

X_В:= X_А; Y_В:= Y_А.

Для визначення S_В кожному стану s_iÎ S_А ставиться у відповідність множина S_ів за допомогою всіляких пар вигляду <s_i, y_m>, де y_m - вихідний сигнал, що відповідає дузі, що є вхідна в стан s_i (рис. 19.3).

Число елементів множини S_ів дорівнює множині різних вихідних сигналів на дугах автомата А, що входять у стан s_іа. Множина станів S_В автомата Мура А_В виходить як об'єднання множин S_ів для всіх s_iÎ S_А:

S_В = È S_ів

^s_i^{Î S}_А

Приклад. S_ів= {< s_i, y₁>, < s_i, y₂>,…,<s_iA,y_m>}

Рис. 19.3. Вхідні в стан s_i дуги із сигналами

Функції l_В і d_У визначаються так.

Кожному стану s_іmв автомата Мура A_В, що преявляє собою пари вигляду <s_i, y_m>, ставиться у відповідність вихідний сигнал y_m. Якщо в автоматі Мілі був перехід d_А(s_i, x_j ) = s_i і при цьому видавався вихідний сигнал l_А (s_i, x_j) = y_k,, то в автоматі Мура А_В буде перехід з кожного стану множини s_ів , породжуваного вершиною s_i, у стан s_hв = <s_h, y_k> під дією того ж вхідного сигналу x_j.

Приклад. Розщеплення стану s_i залежно від вихідних сигналів y_m .

Рис. 19.4. Розщеплення стану s_i

Як початковий стан можна взяти будь Якій стан s_oВ, породжуваний станом s_oА. При порівнянні реакцій Мілі и Мура на усілякі вхідні слова не враховується вихідний сигнал автомата Мура в момент часу t_o.

Приклад. Заданий автомат Мілі (рис. 19.5), потрібно побудувати автомат Мура (рис. 19.6). X_B := X_A ={x_1, x₂}, Y_B :=Y_A ={y_1, y_2, y₃}.

Рис.19.5. Автомат Мілі

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