Алгоритм переходу від довільного кінцевого автомата Милі до еквівалентного йому автоматові Мура

Розглянемо алгоритм переходу на прикладі автомата Мілі, заданого табл.4.1 і табл. 4.2.

1. Ставимо у відповідність кожній парі (zi, xj) автомата Мілі стан zjj автомата Мура (табл.4.7).

Таблиця 4.7

Вхідний сигнал	Стан
z1/z2	z2	z3
x1	z2/z12	z3/z21	z2/z31
x2	z3/z13	z2/z22	z1/z32

2. У множині станів автомата Мура включаємо початковий стан zi, автомата Мілі.

3. Визначаємо число станів автомата Мура:

т=kl+1,

де k - число вхідних сигналів; l - число станів автомата Милі.

4. Визначаємо збіг станів zj автомата Мілі зі станами zij автомата Мура.

З табл. 4.7. видно, що стан zl автомата Мілі збігається зі станами z₁₁, z₃₂ автомата Мура; z₂ - z_l2, z₃₁, z₂₂; z₃ -z₁₃, z21, т.e.

Тому перехід автомата Мілі зі стану z₁ у стан z₂ повинний відповідати всім переходам автомата Мура зі станів z₁₁ z₃₂ у стан z₁₂, z₃₁, z₂₂, перехід з z₁ в z₃ повинен відповідати всім переходам автомата Мура зі стану z_l1, z₃₂ в z₁₃, z₂₁ і т.д.

5. Складаємо таблицю переходів автомата Мура (табл.4.8).

Таблиця 4.8

Вихдний сигнал	y1	y1	y2	y3	y1	y3	y1
Стан	z11	z12	z13	z21	z22	z31	z32
Вхідний сигнал	x1	z12	z21	z31	z31	z21	z21	z12
x2	z13	z22	z32	z32	z22	z22	z13

Якщо стан z_ij входить у множину, що відповідає стану z₂, то в стовпчик табл.4.8 варто записати стани, що знаходяться в колонку для z₂ (табл.4.7). Наприклад, стовпчику табл.4.8 зі станами z₁₂, z₂₂, z₃₁ збігаються зі стовпчиком для z₂ табл.4.7, стовпчик z₁₃, z₂₁ - зі стовпчиком для z₃ і т.д.

6. Визначаємо функцію виходів еквівалентного автомата Мура.

Функція виходів автомата Мура визначається співвідношенням

Для початкового стану z₁₁ значення вихідного сигналу вибирається довільно.

Щоб відзначити вихідними сигналами стан розглянутого автомата (табл.4.8), досить накласти таблицю виходів автомата Мілі (табл.4.2) на таблицю кодування станів автомата Мура (табл.4.7) і кожен стан відзначити тим вихідним сигналом, з яким воно збігається. Початковий стан для даного автомата позначимо буквою у₁, тому що при цьому стовпчик табл.4.8 для початкового стану z₁₁ і стовпчик z₃₂ будуть ідентичні як по станах, так і по оцінці їхніх вихідних сигналів. Тому зазначені стани можна об'єднати.

Дата добавления: 2015-06-27