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

UptoLike

ВУЗ: 

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

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

Рубрика: 

56
êîíêðåòíûõ ñîñòîÿíèé â ôèíàëüíûå êëàññû. Ïðåäëàãàåìûé ñïîñîá ìî-
æåò áûòü îïèñàí ñ ïîìîùüþ ñëåäóþùåé ïðîöåäóðû.
1. Ôîðìèðóåòñÿ ìíîæåñòâî ïàð ñîâìåñòèìûõ ñîñòîÿíèé íà îñíîâà-
íèè ðàçìåòêè êàæäîãî ñòîëáöà òðåóãîëüíîé òàáëèöû.
Äëÿ ðàññìàòðèâàåìîãî àâòîìàòà Ìèëè (òàáë. 5.12) ïî òàáë. 5.13 íà-
õîäèì ñëåäóþùèå ïàðû ñîâìåñòèìûõ ñîñòîÿíèé:
(b
0
, b
3
), (b
1
, b
3
), (b
2
, b
3
), (b
3
, b
4
), (b
4
, b
5
), (b
5
, b
6
),
(b
0
, b
4
), (b
1
, b
4
), (b
2
, b
4
), (b
3
, b
5
), (b
4
, b
8
), (b
5
, b
7
),
(b
0
, b
6
), (b
1
, b
6
), (b
2
, b
6
), (b
3
, b
8
), (b
4
, b
9
), (b
5
, b
11
),
(b
0
, b
7
), (b
1
, b
7
), (b
2
, b
7
), (b
3
, b
9
), (b
4
, b
10
), (b
5
, b
12
),
(b
0
, b
11
), (b
1
, b
11
), (b
2
, b
11
), (b
3
, b
10
), (b
4
, b
12
),
(b
0
, b
12
), (b
1
, b
12
), (b
2
, b
12
),
(b
6
, b
7
), (b
7
, b
8
), (b
8
, b
11
), (b
9
, b
11
), (b
10
, b
11
),
(b
6
, b
8
), (b
7
, b
9
), (b
8
, b
12
), (b
9
, b
12
), (b
10
, b
12
).
(b
6
, b
9
), (b
7
, b
10
),
(b
6
, b
10
), (b
7
, b
11
),
2. Íà îñíîâå ïîëó÷åííîãî ìíîæåñòâà ïðîèçâîäèòñÿ óêðóïíåíèå ãðóïï
ñîâìåñòèìûõ ñîñòîÿíèé, â ðåçóëüòàòå ÷åãî äîëæíà áûòü ïîëó÷åíà ïîë-
íàÿ ñîâîêóïíîñòü ôèíàëüíûõ êëàññîâ, â êàæäîì èç êîòîðûõ âñå ñîñ-
òîÿíèÿ ñîâìåñòèìû ìåæäó ñîáîé. Äëÿ óìåíüøåíèÿ ñëîæíîñòè ýòîé
ïðîöåäóðû âîçìîæíî ïðè ôîðìèðîâàíèè êàæäîãî î÷åðåäíîãî êëàññà
ñîâìåñòèìûõ ñîñòîÿíèé íå ðàññìàòðèâàòü ñîñòîÿíèÿ, óæå âîøåäøèå â
êàêîé-ëèáî èç ñôîðìèðîâàííûõ êëàññîâ.  ÷àñòíîñòè, â ðàññìàòðèâàå-
ìîì ñëó÷àå ñîñòîÿíèå b
0
ñîâìåñòèìî ñ ñîñòîÿíèÿìè b
3
è b
4
, ïðè÷åì
ñîñòîÿíèå b
3
òàê æå ñîâìåñòèìî ñ ñîñòîÿíèåì b
4
, ñëåäîâàòåëüíî, èõ
ìîæíî âêëþ÷èòü â îäèí ôèíàëüíûé êëàññ K
1
. Ñîñòîÿíèå b
0
ñîâìåñòèìî
è ñ ñîñòîÿíèåì b
6
, îäíàêî b
6
íå ñîâìåñòèìî ñ ñîñòîÿíèåì b
3
è íå ìîæåò
âõîäèòü â ýòîò æå ôèíàëüíûé êëàññ. Àíàëîãè÷íàÿ ñèòóàöèÿ îáíàðóæèâà-
åòñÿ ïðè àíàëèçå ñîâìåñòèìûõ ñ b
0
ñîñòîÿíèé b
7
, b
11
, b
12
. Ïîäîáíûì æå
îáðàçîì ôîðìèðóþòñÿ è âñå îñòàëüíûå ôèíàëüíûå êëàññû. Â ðåçóëüòà-
òå áóäóò ïîëó÷åíû ñëåäóþùèå êëàññû ñîâìåñòèìûõ ñîñòîÿíèé:
K
1
= {b
0
, b
3
, b
4
}, K
5
= {b
8
},
K
2
= {b
1
, b
6
, b
7
}, K
6
= {b
9
},
K
3
= {b
2
, b
11
}, K
7
= {b
10
}.
K
4
= {b
5
, b
12
},

Страницы