20. Построение равносильного автомату Мили автомата Мура.

Не каждый автомат Мили может быть представлен как автомат Мура. Однако в определенном смысле эти автоматы являются равносильными.

Пусть автомат М с параметрами (Z, X, Y, f, g) – автомат Мили, а автомат М_u с параметрами (Z', X, Y, f', h) – автомат Мура. Пусть g' и h' – сокращенные реакции

g'_z(w)=g_z(w)

h'_z'(w)=h_z'(ε)h_z'(w)

Автоматы называются равносильными, если множество их реакций на X⁺ совпадают.

Для любого автомата Мура может быть построен равносильный ему автомат Мили. Причем, если автомат Мура сокращен, то и автомат Мили тоже сокращен. На множестве Z и Z' определим отношение R, которое переводит Z в Z', причем делает это таким образом, что f(z,x)≠f'(z,x) для всех x принадлежащих X

M=(Z', X, Y, f, g), где f'([z],x)=[f(z,x)]

g([z],x)=h(f([z],x))

В том случае, если M_u является сокращенным, тогда для всех z и z' принадлежащим Z [z] ≠ [z'], то g[z]= g[z']

Два автомата Мили равносильные автомату Мура, эквивалентны.

21.Построение равносильного автомату Мура автомата Мили.

Для каждого автомата Мили А= (Z, X, Y, f, g) можно задать равносильный автомат Мура В с не более чем |Z|-|Y| состояниями, причем сокращенный, если А - сокращенный. Автомат В будет иметь столько же состояний, сколько их у автомата А, тогда и только тогда, когда А представим как автомат Мура, т. е. когда для всех z и z' из Z и всех х и х' из X из равенства f(z, x)=f(z', x') вытекает равенство g(z, x)=g(z', х').

22. Гомоморфизм и изоморфизм автоматов Мура.

Пусть А= (Z, X, Y, f, h) и А'= (Z', X', Y', f', h') —два автомата Мура. Тройка отображений φ=( φ_z, φ_х, φ_у), где φ_z: ZZ', φ_х: ХХ' и φ_у: YY', называется гомоморфизмом (или, точнее, ZXY-гомоморфизмом) из А в А', если выполнены следующие условия:

1) (φ_z(f(z, x))=f'(φ_z(z),φ_х(х)) - для всех z из Z и всех х из X;

2) φ_у(h(z)) =h'(φ_z(z)) - для всех z из Z

φ называется гомоморфизмом из А на А' (эпиморфизмом), если отображения φ_z, φ_х и φ_у сюръективны. А' называется при этом гомоморфным образом А.

φ называется изоморфизмом из А на А', если ф — гомоморфизм из А на А' и отображения φ_z, φ_х, φ_у биективны. Если существует изоморфизм из А на А', то А и А' называются изоморфными.

Если одно из отображений, входящих в тройку φ, является тождественным, то оно исключается из φ.

Гомоморфный образ автомата Мура имеет в некотором смысле сходную, но, вообще говоря, более простую структуру. Изоморфные автоматы Мура совпадают с точностью до обозначений: говорят, что они равны с точностью до изоморфизма.

Если А' есть Z-гомоморфный образ А, то А' эквивалентен А. Обращение этого высказывания неверно: если два автомата Мура эквивалентны, то не обязательно один из них является гомоморфным образом другого.

Эквивалентность состояний z и φ(z) докажем полной индукцией по длине входных слов w.

Если |w|=0, т. е. w= Λ, =>

φ(f*(z, w))=φ(z)=f'*( φ (z), w) и h_z(w)=h(z)=h'(φ(z)) = h'_φ(z)(w)

Если |w|=l, т. е. w=x для некоторого х из X, то

φ(f*(z, w))= φ(f(z, x))=f'(φ(z), x)=f'*(φ(z), w);

h_z(w)=h_z(x)=h(z)h(f(z,x))=h'(φ(z))h'(φ(f(z,x)))=h'(φ(z))h'(f'(φ(z),x))=h'_φ(z)(x)= =h'_φ(z)(w).

Предположение индукции: для каждого слова v длины n (n принадлежит N) выполняются равенства φ (f*(z, v))=f'*(φ(z), v) и h'_z(v)=h'_φ(z)(v).

φ(f*(z, w))= φ(f(f*(z, v), x))=f'(φ(f*(z, v)), x) = f'(f'*(φ(z),v), x)= f'*(φ(z),w)

h_z(w)=h_z(v)h(f*(z, vx))=h' _φ(z)(v)h'(φ(f*(z, vx)))= h'_φ(z)(v) h'(f'*(φ(z), vx))

h'_φ(z)(vx)=h'_φ(z)(w).

Вторая часть утверждения будет доказана построением двух автоматов А и А'.