Лупал А.М. Теория автоматов (часть 2)
Подождите немного. Документ загружается.
94
Òàáëèöà 8.5 Òàáëèöà 8.6
Ïîëó÷èì S = J
Q
è R = KQ, îòêóäà
QJS =
è
KQR =
.
 ñîîòâåòñòâèè ñ ýòèìè âûðàæåíèÿìè ñõåìà àñèíõðîííîãî JK-
òðèããåðà áóäåò èìåòü âèä, ïðåäñòàâëåííûé íà ðèñ. 8.17, à. Íà
ðèñ. 8.17, á ïðåäñòàâëåíî óñëîâíîå èçîáðàæåíèå àñèíõðîííîãî JK-
òðèããåðà.
Íà ïðàêòèêå îïèñàííûé òðèããåð íå ïðèìåíÿåòñÿ èç-çà ñëîæíîñòè èç-
ãîòîâëåíèÿ è æåñòêèõ òðåáîâàíèé ê äëèòåëüíîñòè âõîäíûõ ñèãíàëîâ.
Òàê æå, êàê è â ñëó÷àå Ò-òðèããåðà, ïðîáëåìà óñòîé÷èâîñòè ýôôåêòèâíî
ðåøàåòñÿ â òðèããåðàõ ñ äâóõñòóïåí÷àòûì óïðàâëåíèåì. Ôóíêöèîíàëü-
íàÿ ñõåìà äâóõñòóïåí÷àòîãî JK-òðèããåðà ïîêàçàíà íà ðèñ. 8.18, à, åãî
óñëîâíîå îáîçíà÷åíèå íà ðèñ. 8.18, á.
JK
RS RS
b b
b
b
Q
J
K
Q
S
R
T
J
K
Ðèñ. 8.15
Ðèñ. 8.16
K
Q
J
bb
K
Q
J
bb
à) á)
Ðèñ. 8.17
95
Îò äâóõñòóïåí÷àòîãî RS-òðèããåðà (ðèñ. 8.3) îíà îòëè÷àåòñÿ íàëè÷è-
åì îáðàòíîé ñâÿçè ñ âûõîäîâ Q è
Q
íà âõîäû ýëåìåíòîâ 1 è 2.
Ñëåäóåò çàìåòèòü, ÷òî àñèíõðîííàÿ óñòàíîâêà ëþáîãî äâóõñòóïåí-
÷àòîãî òðèããåðà â åäèíè÷íîå è íóëåâîå ñîñòîÿíèå (âûõîäû
R
à
è
S
à
)
ïðîèçâîäèòñÿ èìïóëüñàìè ëîãè÷åñêîãî 0. Ñîñòîÿíèÿ îñòàëüíûõ âõîäîâ
ïðè àñèíõðîííîì óïðàâëåíèè áåçðàçëè÷íû. Êîãäà âõîäû
R
à
è
S
à
íåçà-
äåéñòâîâàíû, íà íèõ ñëåäóåò ïîääåðæèâàòü óðîâåíü ëîãè÷åñêîé 1.
Íà îñíîâå JK-òðèããåðà ïóòåì íåñëîæíîé êîììóòàöèè âõîäíûõ êà-
íàëîâ ìîæíî ïîëó÷èòü ñõåìû òðèããåðîâ òèïà RST (ðèñ. 8.19) è òèïà T
(ðèñ. 8.20).
Q
C
J
M
S
K
S
a
R
a
Q
T
C
J
T
T
K
C
S
J
TT
K
R
C
á)
à)
Ðèñ. 8.18
R
S
T
C
J
T
T
K
C
Ðèñ. 8.19
Ðèñ. 8.20
à
à
à
à
96
9. ÌÈÍÈÌÈÇÀÖÈß ÏÎËÍÎÑÒÜÞ ÎÏÐÅÄÅËÅÍÍÛÕ
ÀÂÒÎÌÀÒÎÂ
Ìåòîä ìèíèìèçàöèè ïîëíîñòüþ îïðåäåëåííûõ àáñòðàêòíûõ àâòîìà-
òîâ èçëîæåí â ëèòåðàòóðå. Îñíîâíàÿ èäåÿ ýòîãî ìåòîäà ñîñòîèò â ðàç-
áèåíèè âñåõ ñîñòîÿíèé èñõîäíîãî àáñòðàêòíîãî àâòîìàòà íà ïîïàðíî íå
ïåðåñåêàþùèåñÿ êëàññû ýêâèâàëåíòíûõ ñîñòîÿíèé è çàìåíå êàæäîãî
êëàññà ýêâèâàëåíòíîñòè îäíèì ñîñòîÿíèåì. Òàêèì îáðàçîì, ïîëó÷àþ-
ùèéñÿ â ðåçóëüòàòå ìèíèìàëüíûé àâòîìàò èìååò ñòîëüêî æå ñîñòîÿ-
íèé, íà ñêîëüêî êëàññîâ ýêâèâàëåíòíîñòè ðàçáèâàþòñÿ ñîñòîÿíèÿ èñõîä-
íîãî àâòîìàòà.
Äâà ñîñòîÿíèÿ àâòîìàòà a
m
è a
s
, íàçûâàþòñÿ ýêâèâàëåíòíûìè (a
m
≡ a
s
),
åñëè λ(a
m
,
ξ) = λ(a
s
,
ξ) äëÿ âñåâîçìîæíûõ âõîäíûõ ñëîâ ξ. Åñëè a
m
è a
s
íå ýêâèâàëåíòíû, îíè ðàçëè÷èìû. Áîëåå ñëàáîé ýêâèâàëåíòíîñòüþ ÿâ-
ëÿåòñÿ k-ýêâèâàëåíòíîñòü. Ñîñòîÿíèÿ a
m
è a
s
k-ýêâèâàëåíòíû (a
m
≡
k
à
s
)
åñëè λ(a
m
, ξ
k
) = λ(a
s
ξ
k
) äëÿ âñåâîçìîæíûõ âõîäíûõ ñëîâ ξ
k
äëèíû k.
Åñëè ñîñòîÿíèÿ k-ýêâèâàëåíòíû, îíè k-ðàçëè÷èìû.
Ââåäåííûå îòíîøåíèÿ ýêâèâàëåíòíîñòè è k-ýêâèâàëåíòíîñòè ðåôëåê-
ñèâíû, ñèììåòðè÷íû è òðàíçèòèâíû, ñëåäîâàòåëüíî, îíè ÿâëÿþòñÿ îò-
íîøåíèÿìè ýêâèâàëåíòíîñòè, à ïîòîìó ìîãóò áûòü èñïîëüçîâàíû äëÿ
ðàçáèåíèÿ ìíîæåñòâà À ñîñòîÿíèé àâòîìàòà íà ïîïàðíî íå ïåðåñåêàþ-
ùèåñÿ êëàññû (êëàññû ýêâèâàëåíòíîñòè). Ñîîòâåòñòâóþùèå ðàçáèåíèÿ
íà êëàññû ýêâèâàëåíòíûõ è k-ýêâèâàëåíòíûõ ñîñòîÿíèé áóäåì îáîçíà-
÷àòü
Π
è
Π
k
. Ðàçáèåíèå
Π
ïîçâîëÿåò îïðåäåëèòü èçáûòî÷íûå ýëåìåíòû
â ìíîæåñòâå ñîñòîÿíèé À. Ïóñòü, íàïðèìåð, a
m
è a
s
ýêâèâàëåíòíû. Ýòî
çíà÷èò, ÷òî ñ òî÷êè çðåíèÿ ðåàêöèé àâòîìàòà íà âñåâîçìîæíûå âõîäíûå
ñëîâà íåâàæíî, íàõîäèòñÿ àâòîìàò â ñîñòîÿíèè a
m
èëè a
s
, è îäíî èç íèõ,
íàïðèìåð a
s
, ìîæåò áûòü óäàëåíî èç ìíîæåñòâà A. Åñëè êàæäûé êëàññ
ýêâèâàëåíòíîñòè ñîäåðæèò òîëüêî îäíî ñîñòîÿíèå, ìíîæåñòâî A íåñîê-
ðàòèìî. Åñëè æå îäèí èëè íåñêîëüêî êëàññîâ ñîäåðæàò áîëåå îäíîãî
ýëåìåíòà, âñå ýëåìåíòû, êðîìå îäíîãî â êàæäîì êëàññå ìîãóò áûòü
èñêëþ÷åíû èç ìíîæåñòâà A , â ðåçóëüòàòå ÷åãî ïîëó÷àåòñÿ àâòîìàò ñ
ìèíèìàëüíûìè ÷èñëîì ñîñòîÿíèé.
Àëãîðèòì ìèíèìèçàöèè ÷èñëà ñîñòîÿíèé àâòîìàòà S = {a
1
, A, Z, W, δ,
λ} ñîñòîèò èç ñëåäóþùèõ øàãîâ.
1. Íàõîäÿòñÿ ïîñëåäîâàòåëüíûå ðàçáèåíèÿ
Π
1
,
Π
2
, ...,
Π
k
,
Π
k+1
ìíî-
æåñòâà A íà êëàññû îäíî-, äâóõ-, ..., k, k+1-ýêâèâàëåíòíûõ ñîñòîÿíèé, äî
97
òåõ ïîð ïîêà íà êàêîì-òî k+1-ì øàãå íå îêàæåòñÿ, ÷òî
Π
k+1
=
Π
k
. Íå-
òðóäíî ïîêàçàòü, ÷òî òîãäà ðàçáèåíèå P
k
= P, ò. å. ÷òî k-ýêâèâàëåíòíûå
ñîñòîÿíèÿ ÿâëÿþòñÿ â ýòîì ñëó÷àå ýêâèâàëåíòíûìè è ÷èñëî øàãîâ k,
ïðè êîòîðîì
Π
k
=
Π
, íå ïðåâûøàåò M1, ãäå M ÷èñëî ýëåìåíòîâ â
ìíîæåñòâå A.
2. Â êàæäîì êëàññå ýêâèâàëåíòíîñòè ðàçáèåíèÿ Ï âûáèðàþòñÿ ïî
îäíîìó ýëåìåíòó, êîòîðûå îáðàçóþò ìíîæåñòâî A ñîñòîÿíèé ìèíèìàëü-
íîãî àâòîìàòà S={a
1
', A, Z, W, δ, λ}, ýêâèâàëåíòíîãî àâòîìàòó S.
3. Ôóíêöèè ïåðåõîäîâ δ è âûõîäîâ λ àâòîìàòà îïðåäåëÿþòñÿ íà
ìíîæåñòâå A×Z. Äëÿ ýòîãî â òàáëèöå ïåðåõîäîâ è âûõîäîâ âû÷åðêèâà-
þòñÿ ñòîëáöû, ñîîòâåòñòâóþùèå íå âîøåäøèì âî ìíîæåñòâî A ñîñòî-
ÿíèÿì, à â îñòàâøèõñÿ ñòîëáöàõ òàáëèöû ïåðåõîäîâ âñå ñîñòîÿíèÿ çà-
ìåíÿþòñÿ íà ýêâèâàëåíòíûå èç ìíîæåñòâà A.
4.  êà÷åñòâå a
1
' âûáèðàåòñÿ îäíî èç ñîñòîÿíèé, ýêâèâàëåíòíîå ñî-
ñòîÿíèþ a
1
.  ÷àñòíîñòè, óäîáíî çà a
1
' ïðèíèìàòü ñàìî ñîñòîÿíèå a
1
.
 êà÷åñòâå ïðèìåðà ðàññìîòðèì ìèíèìèçàöèþ àâòîìàòà Ìèëè S,
çàäàííîãî òàáëèöàìè ïåðåõîäîâ è âûõîäîâ (òàáë. 9.1 è 9.2). Íåïîñðåä-
ñòâåííî ïî òàáëèöå âûõîäîâ ïîëó÷èì ðàçáèåíèå
Π
1
íà êëàññû îäíîýê-
âèâàëåíòíûõ ñîñòîÿíèé, îáúåäèíÿÿ â ýêâèâàëåíòíûå êëàññû îäèíàêî-
âûå ñòîëáöû:
Π
1
={B
1
,B
2
}, B
1
={a
1
, a
2
, a
5
, a
7
, a
8
}, B
2
={a
3
, a
4
, a
6
, a
9
, a
10
, a
11
,
a
12
}. Äåéñòâèòåëüíî, äâà ñîñòîÿíèÿ 1-ýêâèâàëåíòíû, åñëè èõ ðåàêöèÿ íà
âñåâîçìîæíûå âõîäíûå ñëîâà äëèíû 1 ñîâïàäàþò, ò. å. ñîîòâåòñòâóþ-
ùèå ýòèì ñîñòîÿíèÿì ñòîëáöû â òàáëèöå âûõîäîâ äîëæíû áûòü îäèíà-
êîâû.
Òàáëèöà 9.1
Òàáëèöà 9.2
Ñòðîèì òàáëèöó
Π
1
(òàáë. 9.3), çàìåíÿÿ ñîñòîÿíèÿ â òàáë. 1 ñîîòâåò-
ñòâóþùèìè êëàññàìè 1-ýêâèâàëåíòíîñòè. Î÷åâèäíî, ÷òî 1-ýêâèâàëåíò-
a
a
a
!
a
"
a
#
a
$
a
%
a
&
a
'
a
a
a
Z
W
W
W
W
W
W
W
W
W
W
W
W
Z
W
W
W
W
W
W
W
W
W
W
W
W
a
a
a
!
a
"
a
#
a
$
a
%
a
&
a
'
a
a
a
Z
a
a
a
#
a
%
a
!
a
%
a
!
a
a
%
a
a
#
a
Z
a
#
a
&
a
$
a
a
'
a
a
$
a
"
a
$
a
&
a
'
a
&
98
íûå ñîñòîÿíèÿ a
m
, a
s
áóäóò 2-ýêâèâàëåíòíûìè, åñëè îíè ïåðåâîäÿòñÿ
ëþáûì âõîäíûì ñèãíàëîì òàêæå â 1-ýêâèâàëåíòíûå.
Òàáëèöà 9.3
Ïî òàáë. 9.3 ïîëó÷àåì ðàçáèåíèå Ï
2
íà êëàññû 2-ýêâèâàëåíòíûõ ñî-
ñòîÿíèé (òàáë. 9.4):
Π
2
={C
1
, C
2
, C
3
, C
4
}, C
1
={a
1
, a
2
}, C
2
={a
5
, a
7
, a
8
},
C
3
={a
3
, a
4
, a
6
, a
9
, a
11
}, C
4
={a
10
, a
12
}.
Àíàëîãè÷íî ïîñòðîèì
Π
3
={D
1
, D
2
, D
3
, D
4
, D
5
}, D
1
={a
1
, a
2
}, D
2
={a
5
,
a
7
}, D
3
={a
8
}, D
4
={a
3
, a
4
, a
6
, a
9
, a
11
}, D
5
={a
10
, a
12
} (òàáë. 9.5) è, íàêîíåö,
Π
4
={E
1
, E
2
, E
3
, E
4
, E
5
}, êîòîðîå ñîâïàäàåò ñ Ï
3
. Ïðîöåäóðà ðàçáèåíèÿ
çàâåðøåíà. Ðàçáèåíèå Ï
3
åñòü ðàçáèåíèå ìíîæåñòâà ñîñòîÿíèé àâòî-
ìàòà Ìèëè S íà êëàññû ýêâèâàëåíòíûõ ìåæäó ñîáîé ñîñòîÿíèé.
Òàáëèöà 9.4
Òàáëèöà 9.5
Âûáåðåì ïðîèçâîëüíî èç êàæäîãî êëàññà D
1
, D
2
, D
3
, D
4
, D
5
ïî îäíî-
ìó ñîñòîÿíèþ. Ïóñòü, íàïðèìåð, A={a
1
, a
5
, a
8
, a
3
, a
10
}. Óäàëÿÿ èç ïåðâî-
íà÷àëüíûõ òàáëèö ïåðåõîäîâ (òàáë. 9.1) è âûõîäîâ (òàáë. 9.2) ëèøíèå
ñîñòîÿíèÿ a
2
, a
7
, a
4
, a
6
, a
9
, a
11
, a
12
, îïðåäåëÿåì ìèíèìàëüíûé àâòîìàò
Ìèëè S
1
(òàáëèöà ïåðåõîäîâ 9.6 è òàáëèöà âûõîäîâ 9.7), ýêâèâàëåíòíûé
àâòîìàòó S.
D
D
D
!
D
"
D
#
a
a
a
#
a
%
a
&
a
!
a
"
a
$
a
'
a
a
a
Z
D
#
D
#
D
"
D
"
D
#
D
D
D
D
D
D
D
Z
D
D
D
"
D
"
D
"
D
"
D
"
D
"
D
"
D
"
D
!
D
!
C
C
C
!
C
"
a
a
a
#
a
%
a
&
a
!
a
"
a
$
a
'
a
a
a
Z
C
"
C
"
C
!
C
!
C
"
C
C
C
C
C
C
C
Z
C
C
C
!
C
!
C
!
C
!
C
!
C
!
C
!
C
!
C
C
B
B
a
a
a
#
a
%
a
&
a
!
a
"
a
$
a
'
a
a
a
Z
B
B
B
B
B
B
B
B
B
B
B
B
Z
B
B
B
B
B
B
B
B
B
B
B
B
99
Òàáëèöà 9.6 Òàáëèöà 9.7
Ïðè ìèíèìèçàöèè àâòîìàòîâ Ìóðà ââîäèòñÿ ïîíÿòèå 0-ýêâèâàëåíò-
íîñòè ñîñòîÿíèé è ðàçáèåíèÿ ìíîæåñòâà ñîñòîÿíèé íà 0-êëàññû: 0-ýêâè-
âàëåíòíûìè íàçûâàþòñÿ ëþáûå îäèíàêîâî îòìå÷åííûå ñîñòîÿíèÿ àâ-
òîìàòîâ Ìóðà. Åñëè äâà 0-ýêâèâàëåíòíûõ ñîñòîÿíèÿ ëþáûì âõîäíûì
ñèãíàëîì ïåðåâîäÿòñÿ â äâà 0-ýêâèâàëåíòíûõ ñîñòîÿíèÿ, òî îíè íàçû-
âàþòñÿ 1-ýêâèâàëåíòíûìè. Âñå äàëüíåéøèå êëàññû ýêâèâàëåíòíîñòè
ñîñòîÿíèé äëÿ àâòîìàòîâ Ìóðà îïðåäåëÿþòñÿ àíàëîãè÷íî ïðèâåäåííî-
ìó âûøå äëÿ àâòîìàòîâ Ìèëè. Â ðåçóëüòàòå ïðèìåíåíèÿ àëãîðèòìà ìè-
íèìèçàöèè ê àâòîìàòó Ìóðà S
3
(òàáë.9.8), èìåþùåìó 12 ñîñòîÿíèé, ïî-
ëó÷èì àâòîìàò S
4
ñ 4 ñîñòîÿíèÿìè (òàáë. 9.9). Îïóñêàÿ ïðîìåæóòî÷-
íûå òàáëèöû, ïðèâåäåì ëèøü ïîñëåäîâàòåëüíîñòü ðàçáèåíèé
Π
0
={B
1
, B
2
, B
3
}.
Òàáëèöà 9.8
B
1
={a
1
, a
2
, a
8
}; B
2
={a
6
, a
9
, a
10
, a
11
, a
12
}; B
3
={a
3
, a
4
, a
5
, a
7
};
Π
1
={C
1
, C
2
, C
3
, C
4
}; C
1
={a
1
, a
2
, a
8
}; C
2
={a
6
, a
9
, a
11
}; C
3
={ a
10
, a
12
};
C
4
={a
3
, a
4
, a
5
, a
7
};
Π
2
={D
1
, D
2
, D
3
, D
4
};
Π
2
=
Π
1
; D
1
=C
1
; D
2
=C
2
; D
3
=C
3
; D
4
=C
4
.
Òàáëèöà 9.9
Åñëè çàäàííûé àâòîìàò ÷àñòè÷íûé, òî
äëÿ òîãî, ÷òîáû âîñïîëüçîâàòüñÿ ðàññìîò-
ðåííûì ìåòîäîì ìèíèìèçàöèè, íåîáõîäè-
ìî åãî äîîïðåäåëèòü òàê, ÷òîáû ìîæíî
áûëî íàéòè ìàêñèìàëüíîå ÷èñëî ýêâèâà-
ëåíòíûõ ñîñòîÿíèé.
W
W
W
!
W
!
W
!
W
W
!
W
W
W
W
W
a
a
a
!
a
"
a
#
a
$
a
%
a
&
a
'
a
a
a
Z
a
a
a
#
a
%
a
!
a
%
a
!
a
a
%
a
a
#
a
Z
a
#
a
%
a
$
a
a
'
a
a
$
a
"
a
$
a
&
a
'
a
&
a
a
#
a
&
a
!
a
Z
W
W
W
W
W
Z
W
W
W
W
W
a
a
#
a
&
a
!
a
Z
a
a
!
a
a
5
a
Z
a
#
a
!
a
!
a
!
a
&
W
W
W
W
!
a
a
$
a
a
!
Z
a
a
!
a
a
!
Z
a
!
a
$
a
a
$
100
10. ÌÅÒÎÄÛ ÊÎÄÈÐÎÂÀÍÈß ÑÎÑÒÎßÍÈÉ
ÀÁÑÒÐÀÊÒÍÛÕ ÀÂÒÎÌÀÒÎÂ
Ïðîöåññ êîäèðîâàíèÿ ñîñòîÿíèé àáñòðàêòíûõ àâòîìàòîâ ÿâëÿåòñÿ
ïåðâûì ýòàïîì êàíîíè÷åñêîãî ìåòîäà ñòðóêòóðíîãî ñèíòåçà àâòîìà-
òîâ. Êîäèðîâàíèå çàêëþ÷àåòñÿ â óñòàíîâëåíèè âçàèìíî îäíîçíà÷íîãî
ñîîòâåòñòâèÿ ìåæäó ìíîæåñòâîì A = {a
1
, ..., a
m
} ñîñòîÿíèé àâòîìàòà è
ìíîæåñòâîì R-êîìïîíåíòíûõ âåêòîðîâ {k
1
, ..., k
m
}, k
m
={λ
m1
, ..., λ
mR
},
ãäå λ
m1
ñîñòîÿíèå r-ãî ýëåìåíòà ïàìÿòè (òðèããåðà). Îáû÷íî êîäèðî-
âàíèå ïðîèçâîäèòñÿ ñ ïîìîùüþ ñèìâîëîâ äâîè÷íîãî ñòðóêòóðíîãî àë-
ôàâèòà (λ
m
∈{1,0}), ïîñêîëüêó ïðè ýòîì ðåøàåòñÿ çàäà÷à îïðåäåëåíèÿ
íåîáõîäèìîãî ÷èñëà òðèããåðîâ, èìåþùèõ äâà óñòîé÷èâûõ ñîñòîÿíèÿ.
Çàâèñèìîñòü ÷èñëà òðèããåðîâ îò êîëè÷åñòâà ñîñòîÿíèé çàäàííîãî àáñò-
ðàêòíîãî àâòîìàòà îïðåäåëÿåòñÿ ôîðìóëîé [2]:
R ≥ ]log
2
M[,
ãäå ]b[ îçíà÷àåò áëèæàéøåå öåëîå ÷èñëî, áîëüøåå b èëè ðàâíîå åìó,
åñëè b öåëîå.
Êîäèðîâàíèå ñîñòîÿíèé àâòîìàòà ìîæíî îñóùåñòâëÿòü ðàçëè÷íûìè
ñïîñîáàìè. Ýòî ìîæåò áûòü ïðîèçâîëüíîå êîäèðîâàíèå, êîãäà êàæäî-
ìó ñîñòîÿíèþ ñòàâèòñÿ â ñîîòâåòñòâèå ñëó÷àéíûé íàáîð äâîè÷íûõ ñèì-
âîëîâ, êîëè÷åñòâî êîòîðûõ ðàâíî R. Ñèíòåçèðîâàííûé íà îñíîâå òàêîãî
êîäèðîâàíèÿ ñòðóêòóðíûé àâòîìàò íå áóäåò îïòèìàëüíûì, òàê êàê, âî-
ïåðâûõ, åãî êîìáèíàöèîííàÿ ñõåìà ìîæåò îáëàäàòü ïîâûøåííîé ñëîæ-
íîñòüþ è, âî-âòîðûõ, ïðè îòñóòñòâèè ñèíõðîíèçàöèè è äâîéíîé ïàìÿòè â
ïðîöåññå ôóíêöèîíèðîâàíèÿ ýòîãî àâòîìàòà ìîãóò ïîÿâèòüñÿ ñîñòÿçà-
íèÿ [4].
ßâëåíèå ñîñòÿçàíèé âîçíèêàåò âñëåäñòâèå òîãî, ÷òî ýëåìåíòû ïàìÿ-
òè èìåþò ðàçëè÷íûå, õîòÿ è äîñòàòî÷íî áëèçêèå, âðåìåíà ñðàáàòûâà-
íèÿ. Êðîìå òîãî, ðàçëè÷íû òàêæå çàäåðæêè ñèãíàëîâ âîçáóæäåíèÿ, ïî-
ñòóïàþùèõ íà âõîäíûå êàíàëû ýëåìåíòàðíûõ àâòîìàòîâ ïî ëîãè÷åñêè-
ìè öåïÿì íåîäèíàêîâîé äëèíû. Åñëè ïðè ïåðåõîäå àâòîìàòà èç îäíîãî
ñîñòîÿíèÿ â äðóãîå äîëæíû èçìåíèòü ñâîè ñîñòîÿíèÿ ñðàçó íåñêîëüêî
òðèããåðîâ (÷òî õàðàêòåðíî äëÿ ïðîèçâîëüíîãî êîäèðîâàíèÿ), òî ìåæäó
íèìè íà÷èíàþòñÿ ñîñòÿçàíèÿ. Òîò òðèããåð, êîòîðûé âûèãðûâàåò ýòè ñî-
ñòÿçàíèÿ, ò. å. èçìåíèò ñâîå ñîñòîÿíèå ðàíüøå, ÷åì äðóãèå ýëåìåíòû
ïàìÿòè, ìîæåò ÷åðåç öåïü îáðàòíîé ñâÿçè èçìåíèòü ñèãíàëû íà âõîäàõ
íåêîòîðûõ òðèããåðîâ äî òîãî, êàê äðóãèå ó÷àñòâóþùèå â ñîñòÿçàíèÿõ
èçìåíÿò ñâîå ñîñòîÿíèå. Ýòî ìîæåò ïðèâåñòè àâòîìàò â ñîñòîÿíèå, íå
101
ïðåäóñìîòðåííîå ãðàôîì. Òîãäà âîçíèêøèå ñîñòÿçàíèÿ íàçûâàþòñÿ êðè-
òè÷åñêèìè ñîñòÿçàíèÿìè èëè ãîíêàìè.
Ãîíêè ìîãóò áûòü óñòðàíåíû ðàçëè÷íûìè ñïîñîáàìè, â òîì ÷èñëå è
ñ ïîìîùüþ ïðîòèâîãîíî÷íîãî êîäèðîâàíèÿ.
10.1. Ïðîòèâîãîíî÷íîå êîäèðîâàíèå
ìåòîäîì ðàçâÿçûâàíèÿ ïàð ïåðåõîäîâ
 ëèòåðàòóðå [4] ïðåäëàãàåòñÿ ìåòîä ïðîòèâîãîíî÷íîãî êîäèðîâà-
íèÿ, îñíîâíàÿ èäåÿ êîòîðîãî ñâîäèòñÿ ê ñëåäóþùåìó.
Ïóñòü (a, β) è (γ, δ) äâå ïàðû äâîè÷íûõ êîäîâ ïðîèçâîëüíîé äëèíû,
íàïðèìåð
α 1|0|1 1 γ 0|1|1 1
β 0|0|1 1 δ 0|1|0 0
Åñëè íåêîòîðûé r-é ðàçðÿä êîäà ïðèíèìàåò îäíî çíà÷åíèå íà ïàðå (α,
β) è ïðîòèâîïîëîæíîå íà ïàðå (γ, δ), òî òàêèå ïàðû êîäîâ íàçûâàþòñÿ
ðàçâÿçàííûìè.
Äîêàçàíà ñëåäóþùàÿ òåîðåìà [3]: â àâòîìàòå, ñîñòîÿíèÿ êîòîðîãî
çàêîäèðîâàíû äâîè÷íûìè êîäàìè êîíå÷íîé äëèíû, ãîíêè îòñóòñòâóþò
òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáûõ äâóõ ïåðåõîäîâ (a
m
, a
s
) è (a
k
, a
l
),
a
s
≠a
l
, ïðîèñõîäÿùèõ ïîä äåéñòâèåì îäíîãî è òîãî æå âõîäíîãî ñèãíàëà,
ñîîòâåòñòâóþùèå ïàðû êîäîâ ðàçâÿçàíû. (Åñëè àâòîìàò ñèíõðîííûé,
òî ðàçâÿçûâàòü íóæíî ïàðû ïåðåõîäîâ, äëÿ êîòîðûõ (a
m
, a
s
)∩(a
k
, a
l
)=∅).
 ýòîé æå ðàáîòå ïðèâåäåí îñíîâàííûé íà ýòîé òåîðåìå àëãîðèòì ïðî-
òèâîãîíî÷íîãî êîäèðîâàíèÿ ñîñòîÿíèé êîíå÷íûõ àâòîìàòîâ, îñíîâíàÿ
èäåÿ êîòîðîãî äîñòàòî÷íî ïðîñòà: ïîñëåäîâàòåëüíî ïðîñìàòðèâàÿ âñå
ïàðû ïåðåõîäîâ, äëÿ êîòîðûõ èìååòñÿ õîòÿ áû îäèí îáùèé âõîäíîé ñèã-
íàë, îñóùåñòâëÿþùèé ýòè ïåðåõîäû, ñëåäóåò ïðèñâîèòü ðàçðÿäàì êî-
äîâ òàêèå çíà÷åíèÿ, ÷òîáû ñóùåñòâóþùèå ïàðû êîäîâ ñîñòîÿíèé áûëè
ðàçâÿçàíû.
Àëãîðèòì ïðîòèâîãîíî÷íîãî êîäèðîâàíèÿ çàêëþ÷àåòñÿ â ïîñëåäîâà-
òåëüíîì ðàçâÿçûâàíèè ïîäëåæàùèõ ðàçâÿçûâàíèþ ïàð ïåðåõîäîâ. Íà
ïðîìåæóòî÷íûõ ýòàïàõ àëãîðèòìà ñîñòîÿíèÿì àâòîìàòà áóäóò ñîîòâåò-
ñòâîâàòü êîäû, çíà÷åíèÿ íåêîòîðûõ ðàçðÿäîâ êîòîðûõ ìîãóò áûòü íå
îïðåäåëåíû. Òàêèå êîäû áóäåì íàçûâàòü íåïîëíûìè. Â äàëüíåéøåì
íåîïðåäåëåííûå ðàçðÿäû êîäîâ îòìå÷àþòñÿ ÷åðòî÷êîé. Ïóñòü (a
m
, a
s
),
(a
k
, a
l
) ïàðà ïåðåõîäîâ àâòîìàòà S, à α, β, γ, δ ñîîòâåòñòâåííî ÷åò-
âåðêà êîäîâ (áûòü ìîæåò, íåïîëíûõ) ñîñòîÿíèé a
m
, a
s
, a
k
, a
l
äëèíû i.
102
Îïåðàöèÿ ðàçâÿçûâàíèÿ ïàðû ïåðåõîäîâ (a
m
, a
s
), (a
k
, a
l
) ñâîäèòñÿ ê íå-
ñêîëüêèì ýòàïàì.
1. Ïîëîæèòü i = 0. Ïåðåéòè ê ï.2.
2. Åñëè i = 0, òî ïåðåõîä ê ï.8, èíà÷å ïåðåõîä ê ï.3.
3. Åñëè ïðè íåêîòîðîì r (1 ≤ r ≤ i) çíà÷åíèÿ r-ãî ðàçðÿäà ÷åòâåðêè α,
β, γ, δ îáðàçóåò íàáîð 0011 èëè íàáîð 1100, òî ïåðåõîä ê ï.9, èíà÷å ê ï.4.
4. Åñëè ïðè íåêîòîðîì r (1 ≤ r ≤ i) çíà÷åíèÿ r-ãî ðàçðÿäà ÷åòâåðêè α,
β, γ, δ îáðàçóåò îäèí èç íàáîðîâ
0 1 1 1 1 1
0 1 1 0 1 0
0 0 1 0 0 0
0 0 1 0 1 1
0 1 0 1 ,
òî ïåðåõîä ê ï.5, èíà÷å ê ï.6.
5. Äîîïðåäåëèòü íåîïðåäåëåííûå çíà÷åíèÿ r-ãî ðàçðÿäà ÷åòâåðêè
α, β, γ, δ òàê, ÷òîáû åãî çíà÷åíèÿ îáðàçîâûâàëè íàáîð 0011. Ïåðåõîä
ê ï.9.
6. Åñëè ïðè íåêîòîðîì r (1 ≤ r ≤ i) çíà÷åíèÿ r-ãî ðàçðÿäà ÷åòâåðêè α,
β, γ, δ îáðàçóåò îäèí èç íàáîðîâ
1 0 0 0 0 0
1 0 0 1 0 1
1 1 0 1 1 1
1 1 0 1 0 0
1 0 1 0 ,
òî ïåðåõîä ê ï.7, èíà÷å ïåðåõîä ê ï.8.
7. Äîîïðåäåëèòü íåîïðåäåëåííûå çíà÷åíèÿ r-ãî ðàçðÿäà ÷åòâåðêè α,
β, γ, δ òàê, ÷òîáû çíà÷åíèÿ ýòîãî ðàçðÿäà îáðàçîâûâàëè íàáîð 1100.
Ïåðåõîä ê ï.9.
8. Äîïîëíèòü êîäû ñîñòîÿíèé àâòîìàòà îäíèì íåîïðåäåëåííûì ðàç-
ðÿäîì. Óâåëè÷èòü r íà åäèíèöó. Ïåðåõîä ê ï.4.
9. Ïàðà ïåðåõîäîâ (a
m
, a
s
), (a
k
, a
l
), ðàçâÿçàíà. Êîíåö.
Äëèíà êîäà, ïîëó÷àåìàÿ â ðåçóëüòàòå ïðèìåíåíèÿ èçëîæåííîãî àëãî-
ðèòìà, â áîëüøèíñòâå ñëó÷àåâ îêàçûâàåòñÿ íåìèíèìàëüíîé, òàê êàê ïðè
ââåäåíèè íîâîãî ðàçðÿäà êîäà ìîãóò ðàçâÿçûâàòüñÿ ïàðû ïåðåõîäîâ,
êîòîðûå óæå áûëè ðàçâÿçàíû ðàíåå. Â ñâÿçè ñ ýòèì æåëàòåëüíî ìèíè-
ìèçèðîâàòü äëèíó ïîëó÷àåìûõ êîäîâ ñîñòîÿíèé, ÷òî äåëàåòñÿ ñëåäóþ-
ùèì îáðàçîì. Èñêëþ÷àåì îäèí èç ðàçðÿäîâ êîäîâ, â ðåçóëüòàòå ÷åãî
103
íåêîòîðûå ïàðû ïåðåõîäîâ ìîãóò îêàçàòüñÿ ñâÿçàííûìè, è ïðèìåíÿåì
àëãîðèòì ðàçâÿçûâàíèÿ ïàð ïåðåõîäîâ. Ïîñëå ýòîãî èñêëþ÷àåì åùå îäèí
ðàçðÿä, âíîâü ïðèìåíÿåì àëãîðèòì ïðîòèâîãîíî÷íîãî êîäèðîâàíèÿ è ò.ä.,
äî òåõ ïîð ïîêà äëèíà êîäà íå ïåðåñòàíåò óìåíüøàòüñÿ. Åñëè â ðåçóëü-
òàòå ðàáîòû àëãîðèòìà çíà÷åíèÿ íå âñåõ ðàçðÿäîâ áóäóò îïðåäåëåíû,
òî èõ ìîæíî äîîïðåäåëèòü ïðîèçâîëüíî.
Ïðîèëëþñòðèðóåì àëãîðèòì ïðîòèâîãîíî÷íîãî êîäèðîâàíèÿ íà ïðè-
ìåðå àâòîìàòà, ôóíêöèÿ ïåðåõîäîâ êîòîðîãî çàäàíà òàáë. 10.1.
Òàáëèöà 10.1
Î÷åâèäíî, ÷òî ïàðû äîëæíû áûòü ðàçâÿçàíû â êàæäîì èç ìàññèâîâ
ïåðåõîäîâ M
1
, M
2
, M
3
, ïðîèñõîäÿùèõ ïîä äåéñòâèåì ñèãíàëîâ Z
1
, Z
2
, Z
3
:
M
1
M
2
M
3
(a
1
, a
2
)(a
1
, a
1
)(a
2
, a
5
)
(a
2
, a
2
)(a
2
, a
3
)(a
3
, a
7
)
(a
3
, a
4
)(a
3
, a
3
)(a
5
, a
5
)
(a
4
, a
4
)(a
4
, a
1
)(a
7
, a
7
)
(a
5
, a
6
)(a
5
, a
3
)
(a
6
, a
6
)
Ðàçâÿçûâàíèå ïàð ïåðåõîäîâ â M
1
íà÷íåì ñ ïåðâîãî ïåðåõîäà (a
1
, a
2
).
Ñîãëàñíî ñôîðìóëèðîâàííîé âûøå òåîðåìå ïàðó (a
1
, a
2
) è (a
2
, a
2
) ðàçâÿ-
çûâàòü íå íàäî èç-çà ñîâïàäåíèÿ ñîñòîÿíèé ïåðåõîäà. Ïåðâàÿ ïàðà ïå-
ðåõîäîâ, êîòîðàÿ ïîäëåæèò ðàçâÿçûâàíèþ, åñòü (a
1
, a
2
), (a
3
, a
4
). Ââîäèì
ïåðåìåííóþ t
1
è îáðàçóåì ïî ýòîé ïåðåìåííîé ÷åòâåðêó (0011) äëÿ ñî-
ñòîÿíèé a
1
, a
2
, a
3
, a
4
. Ðàññìàòðèâàåìàÿ ïàðà ïåðåõîäîâ ðàçâÿçàíà
(òàáë.10.2).
Ïàðå ïåðåõîäîâ (a
1
, a
2
), (a
4
, a
4
) ñîîòâåòñòâóåò ÷åòâåðêà (0011)
(òàáë.10.2), ò. å. ýòà ïàðà òîæå ðàçâÿçàíà.
Ïàðà (a
1
, a
2
),(a
5
, a
6
) îáðàçóåò ÷åòâåðêó (00 ). Äëÿ ðàçâÿçûâàíèÿ
ýòîé ïàðû äîîïðåäåëèì ýòó ÷åòâåðêó äî (0011), äëÿ ÷åãî ñîñòîÿíèÿì a
5
,
a
6
ñòàâèì â ñîîòâåòñòâèå t
1
= 1 (òàáë. 10.3).
a
a
a
!
a
"
a
#
a
$
a
%
Z
a
a
a
"
a
"
a
$
a
$
`
Z
a
a
!
a
!
a
a
!
``
Z
!
a
#
a
%
a
#
a
%