="justify"> · s0 - початковий стан;
·?:S? X ® S - функція переходів;
·?:S ® Y - функція виходів.
Для побудови графа автомата Мура (рис.3) нам необхідно позначити його стану і виходи за допомогою вершин графа, а переходи - за допомогою ребер.
Малюнок 3 - Графічне представлення автомат Мура
Як і у випадку з автоматом Мілі для автомата Мура можливо і табличне представлення (табл.2). ??
Таблиця 2 - Табличне представлення автомата Мура
s ?? 01s0y1s1s2s1y2s1s0s2y2s2s1
1.2 Еквівалентність кінцевих автоматів
Нехай S - алфавіт (кінцеве безліч символів) і S * - множина всіх слів в алфавіті S. Будемо позначати буквою e порожнє слово, тобто зовсім не містить букв (символів з S), а знаком?- Операцію приписування (конкатенації) слів.
Так, ААВ? ва=аавв. Знак? операції приписування часто опускають.
Слова в алфавіті S будемо позначати малими грецькими буквами a, b, g, .... Очевидно, e є одиницею для операції приписування:
ae=ea=a.
Очевидно також, що операція приписування асоціативна, тобто (Ab) g=a (bg).
Таким чином, безліч S * всіх слів в алфавіті S відносно операції приписування є полугруппой з одиницею, тобто моноїд;
S * називають вільним моноїд над алфавітом S.
Визначення 3. Нехай А=(S, X, Y, s 0, d, l) - кінцевий автомат.
Розширеними функціями переходу і виходу автомата А називаються функції
d *: S? X * ® S і l *: S? X * ® Y *,
певні так:
d * (s, e)=s; d * (s, а a)=d * (d (s, а), a);
l * (s, e)=e; l * (s, а a)=l (s, а)? l * (d (s, а), a),
де а - будь-яка буква вхідного алфавіту X, а a - будь-яке слово в алфавіті X, тобто a? X *.
Розширені функції переходів і виходів визначені на множині вхідних слів, на відміну від звичайних функцій переходів і виходів, які визначені на множині вхідних сигналів - букв алфавіту.
Нехай у деякий стан автомата не існує шляху з початкового стану. Іншими словами, в ці стани автомат не може потрапити.
Такі стани автомата називаються недосяжними, решта - досяжними.
Очевидно, що недосяжні стану і переходи з них можна відкинути: вони не впливають на поведінку кінцевого автомата. Дамо формальне визначення.
Визначення 4. Нехай А=(S, X, Y, s 0, d, l) - кінцевий автомат. Стан s? S називається досяжним тоді і тільки тоді, коли
($ a? X *) d * (s 0, a)=s
(т.е. під впливом будь-якого вхідного слова автомат потрапляє в цей стан).
Таким чином, стан s? S кінцевого автомата є недосяжним тоді і тільки тоді, коли
("a? X *) d * (s 0, a)? s
(т.е. під впливом будь-якого слова автомат не переходить в цей стан).
Безліч D досяжних станів КА автомата
А=(S, X, Y, s 0, d, l) будується за допомогою алгоритму, заснованого на індукції.
. Покладемо Q 0={s 0}.
. На i-му кроці будемо будувати безліч Qi станів, досяжних з початкового стану автомата деякого слова довжини не більше ніж i.
Очевидно, що для будь-якого i
Q i + 1=Q i? {D (s, x) | s? Q i, x? X}.
. Ясно також, що не більше ніж за n=| S | кроків Q k + 1=Q k.
Покладемо D=Q k.
Визначення 5. Кінцеві автомати А=(SA, XA, YA, s 0A, d A, l A) і В=(SB, XB, YB, s 0B, d B, l B) називаються еквівалентними, якщо виконані дві умови:
а) їх вхідні алфавіти збігаються:
Х A=Х B=X;
б) реалізовані ними відображення виходів збігаються:
("a? X *) l * A (s 0A, a)=l * B (s 0B, a).
Визначення 6. Прямим твором кінцевих автоматів А=(SA, XA, YA, s 0A, d A, l A) і В=(SB, XB, YB, s 0B, d B, l B).
з однаковий вхідним алфавітом X називається автомат
А? В=(SA? SB, X, YA? YB, (s 0A, s 0B), d A? B, l A? B),
де:
a) ( s A? SA) ( s B? SB) ("x? X) d A? B ((s A, s B), x)=(d A (s A, x), d B (s B, x));
