С.С. Марченков - Избранные главы дискретной математики (1124120), страница 7
Текст из файла (страница 7)
. . , Kr }. Íà÷àëüíûì ñîñòîÿíèåì àâòîìàòà K îáúÿâèì êëàññ K1 , à ôóíêöèþ ïåðåõîäîâ h îïðåäåëèì ñëåäóþùèìîáðàçîì: åñëè ai ∈ A, b̄ ñëîâî èç êëàññà Kj , òî h(ai , Kj ) åñòü òîò (åäèíñòâåííûé) êëàññ Kl , êîòîðûé ñîäåðæèò ñëîâî b̄ai . Êîððåêòíîñòü îïðåäåëåíèÿ ôóíêöèè h ñëåäóåò èç ñâîéñòâà ïðàâîé èíâàðèàíòíîñòè îòíîøåíèÿ∼: åñëè b̄, c̄ ëþáûå ñëîâà èç êëàññà Kj , òî b̄ai , c̄ai áóäóò ïðèíàäëåæàòüîäíîìó è òîìó æå êëàññó Kl .Ëåãêî âèäåòü, ÷òî âñå ñîñòîÿíèÿ àâòîìàòà K äîñòèæèìû èç íà÷àëüíî-êîíå÷íî-àâòîìàòíîé ýêâèâàëåíîñòüþïðàâîé èíâàðèàíòíîñòèêîíå÷íûé èíäåêñ30ãî ñîñòîÿíèÿ K1 : åñëè b̄ ñëîâî èç êëàññà Kj , òî, ¾ïðèìåíÿÿ¿ ê êëàññó K1ñëîâî b̄, ïîëó÷èì êëàññ Kj , ïîñêîëüêó Λ ∈ K1 è Λb̄ = b̄.
Êðîìå òîãî, íåïîñðåäñòâåííî èç îïðåäåëåíèÿ àâòîìàòà K âèäíî, ÷òî êîíå÷íî-àâòîìàòíàÿýêâèâàëåíòíîñòü, ïîðîæäåííàÿ àâòîìàòîì K, ñîâïàäàåò ñ ýêâèâàëåíòíîñòüþ ∼. Òàêèì îáðàçîì, ìû óáåäèëèñü â ñïðàâåäëèâîñòè ñëåäóþùåãîóòâåðæäåíèÿ.Êàæäûé êîíå÷íûé èíèöèàëüíûé àâòîìàò ïîðîæäàåò ïðàâîèíâàðèàíòíîå îòíîøåíèå ýêâèâàëåíòíîñòè êîíå÷íîãî èíäåêñà. Îáðàòíî, êàæäîå ïðàâîèíâàðèàíòíîå îòíîøåíèå ýêâèâàëåíòíîñòèêîíå÷íîãî èíäåêñà åñòü êîíå÷íî-àâòîìàòíîå îòíîøåíèå ýêâèâàëåíòíîñòè.Òåîðåìà 2.1.Ïðèìåíèì ïîëó÷åííûé ðåçóëüòàò, ÷òîáû îõàðàêòåðèçîâàòü êîíå÷íîàâòîìàòíûå ìíîæåñòâà.
Ïóñòü A = (A, Q, f, q1 , F ) êîíå÷íûé àâòîìàò,F = {qj1 , . . . , qjs } è X = D(A). Ñîãëàñíî îïðåäåëåíèÿì èç 1, êîíå÷íîàâòîìàòíîå ìíîæåñòâî X ñîñòîèò èç âñåõ ñëîâ â àëôàâèòå A, êîòîðûåïåðåâîäÿò àâòîìàò A èç íà÷àëüíîãî ñîñòîÿíèÿ q1 â îäíî èç ñîñòîÿíèéqj1 , . . . , qjs . Áóäåì ïðåäïîëàãàòü, ÷òî âñå ñîñòîÿíèÿ qj1 , . . .
, qjs äîñòèæèìû èç ñîñòîÿíèÿ q1 . Ïîíÿòíî, ÷òî â ýòîì ñëó÷àå ìíîæåñòâî X ìîæíîïðåäñòàâèòü â âèäå îáúåäèíåíèÿ s ïîïàðíî íå ïåðåñåêàþùèõñÿ ìíîæåñòâX1 , . . . , Xs , ãäå Xt ñîñòîèò èç âñåõ ñëîâ â àëôàâèòå A, êîòîðûå ïåðåâîäÿò àâòîìàò A èç ñîñòîÿíèÿ q1 â ñîñòîÿíèå qjt (1 6 t 6 s). Îäíàêî, êàêìû îïðåäåëèëè âûøå, ìíîæåñòâî Xt åñòü êëàññ ýêâèâàëåíòíûõ ñëîâ âêîíå÷íî-àâòîìàòíîé ýêâèâàëåíòíîñòè, ïîðîæäåííîé àâòîìàòîì A. Ó÷èòûâàÿ òåïåðü òåîðåìó 2.1, ïðèõîäèì ê ñëåäóþùåìó ðåçóëüòàòó.Âñÿêîå íåïóñòîå êîíå÷íî-àâòîìàòíîå ìíîæåñòâîåñòü îáúåäèíåíèå íåêîòîðîãî ÷èñëà êëàññîâ ïîäõîäÿùåãî ïðàâîèíâàðèàíòíîãî îòíîøåíèÿ ýêâèâàëåíòíîñòè êîíå÷íîãî èíäåêñà. Îáðàòíî, îáúåäèíåíèå ëþáîãî ÷èñëà êëàññîâ ïðîèçâîëüíîãî ïðîâîèíâàðèàíòíîãî îòíîøåíèÿ ýêâèâàëåíòíîñòè êîíå÷íîãî èíäåêñà åñòü êîíå÷íî-àâòîìàòíîåìíîæåñòâî.Òåîðåìà2.2.Òåîðåìà 2.2 äàåò íàì ïåðâîå îïèñàíèå êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ,íå ñâÿçàííîå ñ ïîíÿòèåì êîíå÷íîãî àâòîìàòà.
Åãî óäîáíî èñïîëüçîâàòüäëÿ äîêàçàòåëüñòâà íåïðèíàäëåæíîñòè íåêîòîðûõ ìíîæåñòâ êëàññó êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ. Äëÿ ïðèìåðà ðàññìîòðèì â àëôàâèòå{a1 , a2 } ìíîæåñòâî X , ñîñòîÿùåå èç âñåõ ñëîâ âèäà an1 an2 (n > 1). Äîêàæåì, ÷òî îíî íå ÿâëÿåòñÿ êîíå÷íî-àâòîìàòíûì. Ïóñòü ýòî íå òàê. Òîãäà äëÿ ïîäõîäÿùåãî ïðàâîèíâàðèàíòíîãî îòíîøåíèÿ ýêâèâàëåíòíîñòè31∼ êîíå÷íîãî èíäåêñà ìíîæåñòâî X åñòü îáúåäèíåíèå íåêîòîðîãî ÷èñëà êëàññîâ ýòîé ýêâèâàëåíòíîñòè.
Ïîñêîëüêó ýêâèâàëåíòíîñòü ∼ èìååòëèøü êîíå÷íîå ÷èñëî êëàññîâ, íàéäóòñÿ òàêèå íåðàâíûå ÷èñëà m, n, ÷òînñëîâà am1 , a1 ïðèíàäëåæàò îäíîìó è òîìó æå êëàññó ýêâèâàëåíòíîñòè ∼,nò.å. am1 ∼ a1 . Ââèäó ñâîéñòâà ïðàâîé èíâàðèàíòíîñòè îòíîøåíèÿ ∼ ïîëónn nn n÷àåì äàëåå am1 a2 ∼ a1 a2 . Îäíàêî ñëîâî a1 a2 ïðèíàäëåæèò ìíîæåñòâó X .nÇíà÷èò, ñëîâî am1 a2 òàêæå ïðèíàäëåæèò ìíîæåñòâó X .
Ýòî ïðîòèâîðå÷èòîïðåäåëåíèþ ìíîæåñòâà X .×òîáû ïîëó÷àòü ïðèìåðû áîëåå ñëîæíûõ êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ, ðàññìîòðèì ðÿä îïåðàöèé, êîòîðûå ñîõðàíÿþò êîíå÷íóþ àâòîìàòíîñòü ìíîæåñòâ. Ïåðâûìè â ýòîì ðÿäó áóäóò òåîðåòèêî-ìíîæåñòâåííûåîïåðàöèè äîïîëíåíèÿ, îáúåäèíåíèÿ è ïåðåñå÷åíèÿ.Ïóñòü çàäàí àâòîìàò A = (A, Q, f, q1 , F ) è X = D(A).
Ïîíÿòíî, ÷òîâñå ìíîæåñòâî A∗ ðàçáèâàåòñÿ íà äâà íåïåðåñåêàþùèõñÿ ìíîæåñòâà: ìíîæåñòâî âñåõ ñëîâ, ïîä äåéñòâèåì êîòîðûõ àâòîìàò A èç ñîñòîÿíèÿ q1ïîïàäàåò â îäíî èç ñîñòîÿíèé ìíîæåñòâà F (ïî îïðåäåëåíèþ ýòî åñòüìíîæåñòâî X ), è ìíîæåñòâî âñåõ îñòàëüíûõ ñëîâ, ïîä äåéñòâèåì êîòîðûõàâòîìàò A èç ñîñòîÿíèÿ q1 ïîïàäàåò â ñîñòîÿíèÿ èç Q\F . Ñëåäîâàòåëüíî,ìíîæåñòâî X̄ = A∗ \ X äîïóñêàåòñÿ àâòîìàòîì A1 = (A, Q, f, q1 , Q \ F ).Êàê âèäíî, àâòîìàò A1 îòëè÷àåòñÿ îò àâòîìàòà A òîëüêî âûáîðîì ìíîæåñòâà çàêëþ÷èòåëüíûõ ñîñòîÿíèé.Èòàê, îïåðàöèÿ äîïîëíåíèÿ (äî ìíîæåñòâà A∗ ) íå âûâîäèò çà ïðåäåëû êëàññà êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ.
Ýòîò ðåçóëüòàò ìû ìîãëè áûäîêàçàòü è ïî-äðóãîìó, âîñïîëüçîâàâøèñü òåîðåìîé 2.2.  ñàìîì äåëå,ñîãëàñíî òåîðåìå 2.2 äëÿ ïîäõîäÿùåãî ïðàâîèíâàðèàíòíîãî îòíîøåíèÿýêâèâàëåíòíîñòè ∼ êîíå÷íîãî èíäåêñà ìíîæåñòâî X åñòü îáúåäèíåíèåíåêîòîðîãî ÷èñëà êëàññîâ ýêâèâàëåíòíîñòè ∼. Ïîíÿòíî, ÷òî ìíîæåñòâîX̄ ïðè ýòîì áóäåò ÿâëÿòüñÿ îáúåäèíåíèåì îñòàâøèõñÿ êëàññîâ ýêâèâàëåíòíîñòè ∼. Çíà÷èò, ìíîæåñòâî X̄ òàêæå êîíå÷íî-àâòîìàòíî.Ïåðåéäåì ê îïåðàöèÿì îáúåäèíåíèÿ è ïåðåñå÷åíèÿ. Ìû õîòèì ïîêàçàòü, ÷òî ýòè îïåðàöèè òàêæå íå âûâîäÿò çà ïðåäåëû êëàññà êîíå÷íîàâòîìàòíûõ ìíîæåñòâ.
Ââèäó çàêîíîâ äå Ìîðãàíà äîñòàòî÷íî ðàññìîòðåòü òîëüêî îäíó èç ýòèõ îïåðàöèé, íàïðèìåð, îïåðàöèþ ïåðåñå÷åíèÿ.Ïóñòü X, Y êîíå÷íî-àâòîìàòíûå ìíîæåñòâà, à ïðàâîèíâàðèàíòíûåîòíîøåíèÿ ýêâèâàëåíòíîñòè ∼1 è ∼2 êîíå÷íîãî èíäåêñà âûáðàíû òàê,÷òî X åñòü îáúåäèíåíèå íåêîòîðîãî ÷èñëà êëàññîâ îòíîøåíèÿ ∼1 è Yåñòü îáúåäèíåíèå íåêîòîðîãî ÷èñëà êëàññîâ îòíîøåíèÿ ∼2 . Ïóñòü äàëååK1 , . .
. , Ks âñå êëàññû îòíîøåíèÿ ∼1 , L1 , . . . , Lt âñå êëàññû îòíîøå32íèÿ ∼2 è, íàïðèìåð,X = K1 ∪ . . . ∪ Ku ,Y = L1 ∪ . . . ∪ Lv .Ââåäåì íà ìíîæåñòâå A∗ íîâîå îòíîøåíèå ýêâèâàëåíòíîñòè ∼3 (ïåðåñå÷åíèå îòíîøåíèé ∼1 è ∼2 ). Äëÿ ýòîãî, îòïðàâëÿÿñü îò ðàçáèåíèé {K1 , . . . ,Ks } è {L1 , . . . , Lt } ìíîæåñòâà A∗ , ñîçäàäèì íîâîå ðàçáèåíèå {M1 , .
. . , Mp }ìíîæåñòâà A∗ : ìíîæåñòâà M1 , . . . , Mp ýòî âñå íåïóñòûå ïåðåñå÷åíèÿ âèäà Ki ∩ Lj , ãäå 1 6 i 6 s è 1 6 j 6 t. Ïîíÿòíî, ÷òî p 6 st è {M1 , . . . , Mp } äåéñòâèòåëüíî ðàçáèåíèå ìíîæåñòâà A∗ íà íåïóñòûå ïîïàðíî íå ïåðåñåêàþùèåñÿ ìíîæåñòâà. Çíà÷èò, íà îñíîâå ðàçáèåíèÿ {M1 , . . . , Mp } ìîæíîîïðåäåëèòü îòíîøåíèå ýêâèâàëåíòíîñòè ∼3 , ïîëàãàÿ ñëîâà ā, b̄ ∈ A∗ ýêâèâàëåíòíûìè â ñìûñëå îòíîøåíèÿ ∼3 â òîì è òîëüêî òîì ñëó÷àå, êîãäàā, b̄ ïðèíàäëåæàò îäíîìó è òîìó æå ìíîæåñòâó ðàçáèåíèÿ {M1 , .
. . , Mp }.Ëåãêî âèäåòü, ÷òî îòíîøåíèå ýêâèâàëåíòíîñòè ∼3 ïðîâîèíâàðèàíòíî:åñëè ā ∼3 b̄, òî ïî îïðåäåëåíèþ ýêâèâàëåíòíîñòè ∼3 áóäåò òàêæå ā ∼1 b̄è ā ∼2 b̄. Èç ïîñëåäíèõ äâóõ ñîîòíîøåíèé ñëåäóåò, ÷òî äëÿ ëþáîãî ñëîâà c̄ èìååì āc̄ ∼1 b̄c̄ è āc̄ ∼2 b̄c̄. Âñïîìèíàÿ, ÷òî ∼3 åñòü ïåðåñå÷åíèåîòíîøåíèé ýêâèâàëåíòíîñòè ∼1 è ∼2 , ïîëó÷àåì, ÷òî āc̄ ∼3 b̄c̄. Êðîìå òîãî, èç îïðåäåëåíèÿ ñëåäóåò, ÷òî ∼3 åñòü îòíîøåíèå êîíå÷íîãî èíäåêñà.Îñòàåòñÿ ïðåäñòàâèòü ìíîæåñòâî X ∩ Y â âèäå îáúåäèíåíèÿ íåêîòîðîãî ÷èñëà ìíîæåñòâ M1 , . . .
, Mp . Ïîíÿòíî, ÷òî ýòî áóäóò â òî÷íîñòè âñåìíîæåñòâà Ml , êîòîðûå ÿâëÿþòñÿ íåïóñòûìè ïåðåñå÷åíèÿìè ìíîæåñòâèç ÷èñëà K1 , . . . , Ku ñ ìíîæåñòâàìè èç ÷èñëà L1 , . . . , Lv .Ïîëó÷åííûé âûøå ðåçóëüòàò ìû îôîðìèì â âèäå òåîðåìû.Îïåðàöèè äîïîëíåíèÿ, îáúåäèíåíèÿ è ïåðåñå÷åíèÿ ñîõðàíÿþò êîíå÷íóþ àâòîìàòíîñòü ìíîæåñòâ.Òåîðåìà 2.3.Ñ èñïîëüçîâàíèåì òåîðåìû 2.3 ìîæíî ïîëó÷èòü àíàëîãè÷íûå ðåçóëüòàòû è äëÿ äðóãèõ òåîðåòèêî-ìíîæåñòâåííûõ îïåðàöèé, íàïðèìåð, äëÿîïåðàöèé ðàçíîñòè è ñèììåòðè÷åñêîé ðàçíîñòè:X \ Y = X ∩ Ȳ ,X4Y = (X \ Y ) ∪ (Y \ X).ÓÏÐÀÆÍÅÍÈßÏîñòðîèâ íà ìíîæåñòâå {a1 , a2 }∗ ïîäõîäÿùèå ïðàâîèíâàðèàíòíûåîòíîøåíèÿ ýêâèâàëåíòíîñòè, äîêàçàòü êîíå÷íóþ àâòîìàòíîñòü ñëåäóþùèõ ìíîæåñòâ:3.a) {Λ};b) {a1 };c) {Λ, a1 , a2 };33d) {an1 a2 : n > 0}.Äëÿ ëþáîãî n > 2 îïðåäåëèòü íà ìíîæåñòâå {a1 , a2 }∗ ïðàâîèíâàðèàíòíóþ ýêâèâàëåíòíîñòü, èìåþùóþ ðîâíî n êëàññîâ ýêâèâàëåíòíîñòè.5.
Ïî àíàëîãèè ñ ïðàâîèíâàðèàíòíîé ýêâèâàëåíòíîñòüþ îïðåäåëèòüíà ìíîæåñòâå A∗ ëåâîèíâàðèàíòíóþ ýêâèâàëåíòíîñòü: åñëè ā ∼ b̄ è c̄ ïðîèçâîëüíîå ñëîâî èç A∗ , òî c̄ā ∼ c̄b̄. Äîêàçàòü äëÿ ëåâîèíâàðèàíòíîéýêâèâàëåíòíîñòè àíàëîã òåîðåìû 2.2.6. Ïîëüçóÿñü òåîðåìîé 2.3, äîêàçàòü êîíå÷íóþ àâòîìàòíîñòü ñëåäóþùèõ ìíîæåñòâ:a) ëþáîå êîíå÷íîå ìíîæåñòâî ñëîâ â àëôàâèòå A; b) ëþáîå ìíîæåñòâîâèäà A∗ \ X , ãäå X êîíå÷íîå ìíîæåñòâî ñëîâ â àëôàâèòå A; c) ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå A, èìåþùèõ âèä ani ãäå 1 6 i 6 k è n > 1; d)ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå {a1 , a2 }, êîòîðûå èìåþò ÷åòíóþ äëèíó,íà÷èíàþòñÿ áóêâîé a1 è â êîòîðûõ áóêâû a1 , a2 ÷åðåäóþòñÿ.4. 3. Íåäåòåðìèíèðîâàííûå àâòîìàòûÄàëåå ìû ðàññìîòðèì äâå íîâûå, ñóãóáî àâòîìàòíûå îïåðàöèè.
×òîáû ïîêàçàòü, ÷òî îíè íå âûâîäÿò çà ïðåäåëû êëàññà êîíå÷íî-àâòîìàòíûõìíîæåñòâ, íàì ïðèäåòñÿ ïðèáåãíóòü ê òåõíè÷åñêîìó ïðèåìó, êîòîðûéïðîùå âñåãî îáúÿñíèòü, åñëè íåêîëüêî ðàñøèðèòü ââåäåííîå âûøå ïîíÿòèå àâòîìàòà. Ðå÷ü ïîéäåò î òàê íàçûâàåìûõàâòîìàòàõ. Ñ ñîäåðæàòåëüíîé òî÷êè çðåíèÿ íåäåòåðìèíèðîâàííûé àâòîìàò îòëè÷àåòñÿ îò ðàíåå ðàññìîòðåííîãî (äåòåðìèíèðîâàííîãî) àâòîìàòà òîëüêî òåì, ÷òî ôóíêöèÿ ïåðåõîäà íåäåòåðìèíèðîâàííîãî àâòîìàòàïîçâîëÿåò åìó â êàæäîì ñîñòîÿíèè ïîä äåéñòâèåì ëþáîé âõîäíîé áóêâû ïåðåõîäèòü â îäíî èç íåñêîëüêèõ âîçìîæíûõ ñîñòîÿíèé. Ðàçóìååòñÿ,ýòà ñïîñîáíîñòüèìååò ÷èñòî âîîáðàæàåìûé õàðàêòåð è â ðåàëüíûõ àâòîìàòè÷åñêèõ óñòðîéñòâàõ íå âñòðå÷àåòñÿ.Îäíàêî ïðè åå íàëè÷èè àâòîìàò ïðèîáðåòàåò íîâûå âîçìîæíîñòè, ïîçâîëÿþùèå â ðÿäå ñëó÷àåâ ïðîùå ðåøàòü ïîñòàâëåííûå çàäà÷è. Âìåñòå ñòåì êëàññ ìíîæåñòâ, äîïóñêàåìûõ íåäåòåðìèíèðîâàííûìè àâòîìàòàìè,íå ïîïîëíÿåòñÿ íîâûìè (íå êîíå÷íî-àâòîìàòíûìè) ìíîæåñòâàìè.Íåäåòåðìèíèðîâàííûé àâòîìàò A, êàê è îáû÷íûé êîíå÷íûé àâòîìàò,çàäàåòñÿ íàáîðîì (A, Q, f, q1 , F ), ãäå A, Q, q1 , F èìåþò òîò æå ñìûñë, ÷òîè ðàíåå.
Îòëè÷èå ñîñòîèò â ôóíêöèè ïåðåõîäîâ f . Äëÿ íåäåòåðìèíèðîâàííîãî àâòîìàòà ôóíêöèÿ f , âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ (îäíîçíà÷íûì)îòîáðàæåíèåì ìíîæåñòâà A × Q â ìíîæåñòâî Q. Ôóíêöèþ f ñëåäóåò ðàññìàòðèâàòü êàê ôóíêöèþ, îòîáðàæàþùóþ ìíîæåñòâî A×Q â ìíîæåñòâîíåäåòåðìèíèðîâàííûõíåäåòåðìèíèðîâàííîãî ïåðåõîäà342Q \ {∅} âñåõ íåïóñòûõ ïîäìíîæåñòâ ìíîæåñòâà Q, ëèáî êàê ñïåöèàëüíûé âèä ñîîòâåòñòâèÿ ìåæäó ìíîæåñòâàìè A × Q è Q. Èòàê, äëÿ ëþáîéïàðû (ai , qj ) çíà÷åíèåì ôóíêöèè f áóäåì ñ÷èòàòü íåêîòîðîå íåïóñòîåïîäìíîæåñòâî ìíîæåñòâà Q.Ïóñòü ā = ai1 ai2 .
. . ain ñëîâî â àëôàâèòå A.  íåäåòåðìèíèðîâàííîìàâòîìàòå A ýòîìó ñëîâó ñîîòâåòñòâóåò, âîîáùå ãîâîðÿ, íåñêîëüêî ïîñëåäîâàòåëüíîñòåé ñîñòîÿíèé äëèíû n (ïóòåé äëèíû n â äèàãðàììå Ìóðà).Áîëåå òî÷íî, ïóñòü, íàïðèìåð, f (ai1 , q1 ) = {qj1 , . . .
, qjs }, ãäå s > 1. Òîãäà ïîä äåéñòâèåì áóêâû ai1 àâòîìàò A èç ñîñòîÿíèÿ q1 ìîæåò ïåðåéòèâ ëþáîå èç ñîñòîÿíèé qj1 , . . . , qjs . Ïðåäïîëîæèì äàëåå, ÷òîf (ai2 , qj1 ) = {qk1 , . . . , qkt }, . . . , f (ai2 , qjs ) = {ql1 , . . . , qlu }.Òîãäà ïîä äåéñòâèåì ñëîâà ai1 ai2 àâòîìàò A ìîæåò ïåðåéòè â ëþáîå èç ñîñòîÿíèé qk1 , . . . , qkt , . . . , ql1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
