Теория автоматов. Лупал А.М. - 43 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

43
 ìîìåíò t = 0 àâòîìàò íàõîäèòñÿ â ñîñòîÿíèè a
0
. Ïðè ïîäà÷å â ïîñ-
ëåäóþùèå ìîìåíòû âðåìåíè êàæäîãî âõîäíîãî ñèãíàëà z(t) àâòîìàò ïå-
ðåõîäèò â íîâîå ñîñòîÿíèå è âûðàáàòûâàåò âûõîäíîé ñèãíàë w(t).
Ïîñêîëüêó äëÿ àáñòðàêòíîãî àâòîìàòà ïîðÿäîê íóìåðàöèè ñîñòîÿíèé,
îòëè÷íûõ îò a
0
, áåçðàçëè÷åí, ìîæíî ñ÷èòàòü, ÷òî áóêâà z(1) = z
0
ïåðâîãî
âõîäíîãî ñëîâà èç òàáë. 5.3 ïåðåâîäèò àâòîìàò â ñîñòîÿíèå a
1
. Ïðè ýòîì
âûðàáàòûâàåòñÿ âûõîäíîé ñèãíàë w(1) = β. Áóêâà z(2) = z
0
ïåðåâîäèò àâòî-
ìàò èç ñîñòîÿíèÿ a
1
â ñîñòîÿíèå a
2
è îáåñïå÷èâàåò âûðàáîòêó âûõîäíîãî
ñèãíàëà w(2) = β. Âõîäíàÿ áóêâà z(3) = z
0
ïåðåâîäèò àâòîìàò èç a
2
â a
3
.
Ýòîìó ïåðåõîäó ñîîòâåòñòâóåò âûõîäíîé ñèãíàë w(3) = w
1
. Áóêâîé z(4) = a
àâòîìàò ïåðåâîäèòñÿ â ñîñòîÿíèå a
4
ñ âûäà÷åé âûõîäíîãî ñèãíàëà w(4) = w
0
.
Ïîñëåäíåé âî âõîäíîì ñëîâå áóêâîé z(5) = a àâòîìàò, ñîãëàñíî óñëîâèþ,
äîëæåí ïåðåâîäèòüñÿ â ñîñòîÿíèå a
0
. Ýòîìó ïåðåõîäó ñîîòâåòñòâóåò âû-
õîäíîé ñèãíàë w(5) = w
0
. Íà÷àëüíûå îòðåçêè z(1)z(2), w(1)w(2) âòîðîãî âõîä-
íîãî è âûõîäíîãî ñëîâ ñîâïàäàþò ñ ñîîòâåòñòâóþùèìè íà÷àëüíûìè îòðåç-
êàìè ïåðâîãî âõîäíîãî è âûõîäíîãî ñëîâ, ïîýòîìó ïåðâûå äâà ïåðåõîäà äëÿ
âòîðîãî âõîäíîãî ñëîâà ñîâïàäàþò ñ óæå ïîñòðîåííûìè. Ïîñëåäóþùèå
ïåðåõîäû äëÿ ýòîãî ñëîâà ñòðîÿòñÿ òî÷íî òàê æå, êàê è äëÿ ïåðâîãî ñëîâà.
Çàòåì àíàëîãè÷íûì îáðàçîì ñòðîÿòñÿ ïåðåõîäû äëÿ îñòàëüíûõ âõîäíûõ è
âûõîäíûõ ñëîâ (ñì. òàáë. 5.3).
Ãðàô àâòîìàòà Ìóðà ïðèâåäåí íà ðèñ. 5.2. Îí ñòðîèòñÿ ïî÷òè òàê
æå, êàê è äëÿ àâòîìàòà Ìèëè. Ïåðâîå îòëè÷èå ñîñòîèò â òîì, ÷òî âû-
õîäíûå ñèãíàëû çàïèñûâàþòñÿ â âåðøèíàõ, òàê êàê âûõîäíîé ñèãíàë
àâòîìàòà Ìóðà â êàæäûé ìîìåíò âðåìåíè îïðåäåëÿåòñÿ òîëüêî
ñîñòîÿíèåì è íå çàâèñèò îò âõîäíîãî ñèãíàëà.
z
1
z
1
z
1
z
1
z
1
z
1
z
1
z
1
z
z
0
z
0
z
0
z
0
z
0
z
0
z
0
a
1
3
a
3
a
2
a
9
a
8
a
1
0
a
1
1
a
1
7
a
1
4
a
5
a
8
a
1
5
a
1
8
a
1
9
a
2
0
w
0
w
1
w
0
w
0
w
1
w
0
w
0
w
0
w
0
w
0
w
0
w
1
w
1
w
1
w
0
a
1
a
2
a
1
2
a
7
a
1
6
a´
0
a
´
0
a
´
0
a
´
0
a
´
0
a´´
0
a
´
´
0
a
´
´
0
a
´
´
0
a
´
´
0
w
0
β
β
β
β
β
αα
αα
α
α
α
αα
αα
αα
α
w
1
Ðèñ. 5.2

Страницы