>:(h}

Si(h)

S7(h)

&

Si(h*1l

Sub)

t in/

&c

S2M

5?(h)

Рис.3.11. Принципиальная схема конечного автомата

Итак, проведен полный синтез конечного автомата . Результатом синтеза автомата может быть как аппаратурная, так и программная его реализация. В последнем случае булевы функции переходов и выходов программируются с помощью имеющихся в математическом обеспечении ЭВМ логических функций и выводятся из ЭВМ на соответствующие внешние устройства. Например, в случае программной реализации автомата в микропроцессорной стойке устройства ЧПУ исполнительными (внешними) устройствами могут быть различные органы станка: револьверная головка, магазин инструментов, приводы подач и главного движения, насос подачи СОЖ и т.п. В случае программного синтеза автомата, рассмотренного выше (см.рис.3.9), на языке Basic и булевыми функциями переходов и выходов (3.10),(3.11), программа, реализующая этот автомат, имеет вид:

5REM ПРОГРАММА АВТОМАТ

10 INPUT ВВЕДИТЕ НАЧАЛЬНОЕ СОСТОЯНИЕ S1,S2 S1,S2 15 INPUT ВЕДИТЕ ВХОДНОЕ ВОЗДЕЙСТВИЕ ХХ1 20I=X1:GOSUB200 25 H1=I1

30I=S1:GOSUB200 35 Z1=I1

40 I=S2:GOSUB 200

45 Z2=I1

50 S8=H1*Z1*Z2+X1*S1*Z2

55 IF S8>0 THEN S8=1

60 S9 = H1*S1*Z2+X1*Z1*Z2+X1*Z1*S2

65 IF S9>0 THEN S9=1

70 Y=(X1+Z1+S2)*(H1+S1+Z2)

75 IF Y>0 THEN Y=1 80 S1=S8: S2=S9

85 PRINT ! 1, 0! S1= SI, S2= S2, Y= Y,X= XI

90 INPUTPAEOTATb ДАЛЬШЕ ДА(1), НЕТ (0) R 95 IF R=1 THEN 15 100 END

200 REM ПОДПРОГРАММА ИНВЕРСИИ 205 I1=0:IFI=0 THEN 11=1 210 RETURN

Приведенная программа не имеет каких-либо особенностей в работе, необходимо лишь отметить, что поскольку в языке Basic нет функции инверсии, то эта функция организуется в виде подпрограммы, а логические функции дизъюнкции и конъюнкции заменяются соответственно сложением и умножением с последующей нормализацией их результата к логической единице (см. строку N55 или N65 программы)[5].

3.10. ПОКРЫТИЕ И ЭКВИВАЛЕНТНОСТЬ АВТОМАТОВ

Автомат M1 покрывает автомат М, есливходнойивыходнойалфавит у этих автоматов общие, переработка входных слов заданной длины r производиться одинаковым образом, а число внутренних состояний S1 автоматаМу меньше, чем у автоматам, т.е.

M = {X,S,Y,y/,v}

Vj (Sj, xr) = v(s, xr) для любых xr eX

при этом пишут M1>M (автомат M1 покрывает М).

Отношение покрытия на множестве автоматов есть квазипорядок в силу транзитивность и рефлексивности. Автоматы M1 и М эквивалентны, если взаимно покрывают друг друга, т.е. M1> M и M1< M, вэтомслучае пишут M1=M.

Эквивалентные автоматы неразличимы по реакции на выходе, но могут иметь различное количество внутренних состояний и, следовательно, могут отличаться внутренними состояниями при одинаковых входных воздействиях.

Очевидно, что эквивалентность автоматов рефлексивна, симметрична и транзитивна.

3.11. ЭКВИВАЛЕНТНЫЕ СОСТОЯНИЯ

Состояния st и Sj называются r-эквивалентными, если для любого входного слова х длиной r(xr) соответствующие функции выхода одинаковы, т.е.

vr(si>xr)=vr(sj,xr) .(3.13)

В этом случае будем писать st Er Sj или (si,sj) eG(Er), где Er - отношение эквивалентности, a G(Er) - график отношения эквивалентности. Если (3.13) выполняется для любых г, то состояния sh и sj эквивалентны и пишут st, Е Sj или (sSj) eG(E).

Отношение r- эквивалентности и эквивалентности порождают на множестве S*S разбиение на классы эквивалентности.

Классы эквивалентности относительны E1t объединяют множества всех пар состояний, каждое из которых (состояние) перерабатывает любой входной символ (букву) из входного алфавита в одинаковый выходной символ, т. е.