Составители:
57
3. Ïðîèçâîäèòñÿ àíàëèç ïîëó÷åííûõ ôèíàëüíûõ êëàññîâ íà óäîâ-
ëåòâîðåíèå óñëîâèÿì ïîëíîòû è çàìêíóòîñòè. Ïðîâåðêà óñëîâèÿ ïîëíî-
òû î÷åâèäíà è íå âûçûâàåò çàòðóäíåíèé, à ïðîâåðêà óñëîâèÿ çàìêíóòî-
ñòè âûïîëíÿåòñÿ ïî òàáëèöå ïåðåõîäîâ-âûõîäîâ äëÿ âñåõ ñîñòîÿíèé
àâòîìàòà. Åñëè êàêèå-ëèáî äâà ñîñòîÿíèÿ, âõîäÿùèå â îäèí èç âûáðàí-
íûõ ôèíàëüíûõ êëàññîâ, ïåðåâîäÿòñÿ íåêîòîðûì âõîäíûì ñèãíàëîì â
ñîñòîÿíèÿ, ïðèíàäëåæàùèå ðàçíûì êëàññàì, òî íóæíî âûáðàòü íîâîå
ðåøåíèå è ïðîâåðèòü åãî íà çàìêíóòîñòü.
Äëÿ ðàññìàòðèâàåìîãî àâòîìàòà ïðè ïðîâåðêå ôèíàëüíûõ êëàññîâ
íà çàìêíóòîñòü îêàçûâàåòñÿ, ÷òî ïðèíàäëåæàùèå êëàññó K
2
ñîñòîÿíèÿ
b
6
è b
7
ñèãíàëîì a ïåðåâîäÿòñÿ â ñîñòîÿíèÿ, ïðèíàäëåæàùèå ðàçíûì
êëàññàì (b
6
a→ b
7
∈ K
1
, à b
7
a→ b
0
∈ K
2
), ò. å. óñëîâèå çàìêíóòîñòè
íå âûïîëíÿåòñÿ. Ñëåäîâàòåëüíî, íåîáõîäèìî îäíî èç ýòèõ ñîñòîÿíèé (íà-
ïðèìåð, b
7
) ïåðåíåñòè â äðóãîé êëàññ, íå íàðóøàÿ ïðè ýòîì óñëîâèå çàì-
êíóòîñòè. Òàêèì êëàññîì ìîæåò áûòü êëàññ K
5
. Â ðåçóëüòàòå áóäåò
ïîëó÷åíî îêîí÷àòåëüíîå ìíîæåñòâî ôèíàëüíûõ êëàññîâ, ñîâïàäàþùèõ
ñ ñîñòîÿíèÿìè ìèíèìèçèðîâàííîãî àâòîìàòà C
c
0
= K
1
= {b
0
, b
3
, b
4
}, c
3
= K
4
= {b
5
, b
12
}, c
6
= K
7
= {b
10
}.
c
1
= K
2
= {b
1
, b
6
}, c
4
= K
5
= {b
7
, b
8
},
c
0
= K
3
= {b
2
, b
11
}, c
5
= K
6
= {b
9
}.
4. Ñòðîèòñÿ òàáëèöà ïåðåõîäîâ-âûõîäîâ ìèíèìèçèðîâàííîé íîð-
ìàëüíîé ôîðìû çàäàííîãî àâòîìàòà. Äàëåå ïî ýòîé òàáëèöå ìîæíî ïî-
ñòðîèòü ãðàô ïåðåõîäîâ ìèíèìèçèðîâàííîãî àâòîìàòà. Ñîñòîÿíèÿ ïåðå-
õîäîâ è âûõîäíûå ñèãíàëû â ýòîì àâòîìàòå îïðåäåëÿþòñÿ ïî ïåðåõî-
äàì è âûõîäíûì ñèãíàëàì òîãî ñîñòîÿíèÿ, êîòîðîå íàèáîëåå ïîëíî
îïðåäåëåíî.
Òàáëèöà 5.14
c t
α
z
z
c
c
w/
c
/β c
"
/β
c
c
"
w/
c
/β c
!
/β
c
c
w/
c
w/
c
0
w/
c
!
c
"
w/
c
w/
c
w/
c
"
c
0
w/
c
#
w/
c
$
/β
c
#
c
"
w/
c
"
w/
c
$
c
w/
c
!
w/
Страницы
- « первая
- ‹ предыдущая
- …
- 55
- 56
- 57
- 58
- 59
- …
- следующая ›
- последняя »
