Page 46 - 4128

випадку кожен стан a i початкового автомата Мілі породжує
стільки станів автомата Мура, скільки різних вихідних
сигналів створюється в початковому автоматі при попаданні в
стан a i. Розглянемо перехід від автомата Мілі S a до автомата
Мура S b на прикладі автомата (рис. 2.2).
Як випливає з рис. 2.2 для автомата S a при попаданні в
стан а 1 виробляються вихідні сигнали W 2, W 4, W 5, при
попаданні в а 2 – W 1, W 2, a 3 – W 2, a 4 – W 3. Кожній парі стан a i -
вихідний сигнал W j, який виробляється при попаданні в цей
стан, поставимо у відповідність стан b k еквівалентного
автомата Мура S b з тим же вихідним сигналом W j : b 1 = (a 1,
W 2), b 2 = (a 1, W 4), b 3 = (a 1, W 5), b 4 = (a 2, W 1), b 5 = (a 2, W 2), b 6 =
(a 3, W 2), b 7 = (a 4, W 3), тобто кожен стан a i автомата Мілі
породжує деяку безліч A i станів еквівалентного автомата
Мура: а1 = { b 1, b 2, b 3}, а2 = { b 4, b 5 }, а3 = { b 6 }, а4 = { b 7 }.
Як видно, в еквівалентному автоматі Мура кількість
станів 7. Для побудови графа S b поступаємо таким чином.
Оскільки в автоматі S a є перехід із стану а 1 в стан а 2 під дією
сигналу z 1 з видачею W 1, то з безлічі станів а1 = {b 1, b 2, b 3},
породжуваних станом а 1 автомата S a в автоматі S b повинен
бути перехід в стан (a 3, W 2) = b 6 під дією сигналу Z 2 і т.д. Граф
еквівалентного автомата Мура представлений на рис. 2.6.

45