С.С. Марченков - Избранные главы дискретной математики (1124120), страница 9
Текст из файла (страница 9)
Òåîðåìà äîêàçàíà.ÓÏÐÀÆÍÅÍÈßÎòïðàâëÿÿñü îò ìíîæåñòâ {a1 } è {a2 }, ïîñòðîèòü ñ ïîìîùüþ îïåðàöèé îáúåäèíåíèÿ, ïðîèçâåäåíèÿ è èòåðàöèè êîíå÷íî-àâòîìàòíîå ìíîæåñòâî èç çàäà÷è 2e.9. Ïóñòü ā ïðîèçâîëüíîå ñëîâî â àëôàâèòå A. Ñêîëüêî ðàç íóæíîïðèìåíèòü îïåðàöèþ èòåðàöèè, ÷òîáû ïîëó÷èòü ìíîæåñòâî A∗ \ {ā} èçìíîæåñòâ {a1 }, . .
. , {ak } ñ ïîìîùüþ îïåðàöèé îáúåäèíåíèÿ, ïðîèçâåäåíèÿ è èòåðàöèè?8.39 5. Ðåãóëÿðíûå ìíîæåñòâà. Òåîðåìà ÊëèíèÊàê ìû âèäåëè â 2, êîíå÷íî-àâòîìàòíûå ìíîæåñòâà ìîæíî îïðåäåëÿòü áåç èñïîëüçîâàíèÿ êîíå÷íûõ àâòîìàòîâ. Åùå îäíî àëãåáðàè÷åñêîåîïðåäåëåíèå êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ ïðåäëîæåíî Ñ. Êëèíè.Ââåäåì ïîíÿòèÿíàä àëôàâèòîì A è ïàðàëëåëüíî îïðåäåëÿåìîãî èìâ àëôàâèòå A.1.
∅ ÿâëÿåòñÿ ðåãóëÿðíûì âûðàæåíèåì íàä àëôàâèòîì A è çàäàåòïóñòîå ðåãóëÿðíîå ìíîæåñòâî.2. Λ ÿâëÿåòñÿ ðåãóëÿðíûì âûðàæåíèåì íàä àëôàâèòîì A è çàäàåòðåãóëÿðíîå ìíîæåñòâî {Λ}, ñîñòîÿùåå èç îäíîãî ïóñòîãî ñëîâà.3. Åñëè ai áóêâà àëôàâèòà A, òî ñèìâîë ai ÿâëÿåòñÿ ðåãóëÿðíûìâûðàæåíèåì íàä àëôàâèòîì A è çàäàåò ðåãóëÿðíîå ìíîæåñòâî {ai }, ñîñòîÿùåå èç îäíîáóêâåííîãî ñëîâà ai .4. Ïóñòü α, β ðåãóëÿðíûå âûðàæåíèÿ íàä àëôàâèòîì A, êîòîðûåîïðåäåëÿþò ðåãóëÿðíûå ìíîæåñòâà X, Y ñëîâ â àëôàâèòå A. Òîãäàðåãóëÿðíîãî âûðàæåíèÿðåãóëÿðíîãî ìíîæåñòâà(α ∪ β),(αβ),(α)∗ñóòü ðåãóëÿðíûå âûðàæåíèÿ íàä àëôàâèòîì A, êîòîðûå îïðåäåëÿþò ñîîòâåòñòâåííî ðåãóëÿðíûå ìíîæåñòâà X ∪ Y, X · Y è X ∗ .Ïðè çàïèñè ðåãóëÿðíûõ âûðàæåíèé ìû áóäåì èíîãäà îïóñêàòü ñêîáêè,ñ÷èòàÿ, ÷òî îïåðàöèÿ ∗ èìååò áîëåå âûñîêèé ïðèîðèòåò, ÷åì îïåðàöèè ∪è ·, à îïåðàöèÿ · áîëåå âûñîêèé ïðèîðèòåò, ÷åì îïåðàöèÿ ∪.Èç 1 íàì èçâåñòíî, ÷òî ìíîæåñòâà ∅, {Λ} è {ai } ÿâëÿþòñÿ êîíå÷íîàâòîìàòíûìè, à èç 2,4 ÷òî îïåðàöèè îáúåäèíåíèÿ, ïðîèçâåäåíèÿ èèòåðàöèè ñîõðàíÿþò êîíå÷íóþ àâòîìàòíîñòü ìíîæåñòâ.
Òåì ñàìûì ìûäîêàçàëè â îäíó ñòîðîíó ñëåäóþùóþ òåîðåìó.Êëàññ êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ ñîâïàäàåò ñ êëàññîì ðåãóëÿðíûõ ìíîæåñòâ.Òåîðåìà 2.7(Ñ. Êëèíè).Äîêàæåì òåïåðü, ÷òî âñÿêîå êîíå÷íî-àâòîìàòíîå ìíîæåñòâî ÿâëÿåòñÿðåãóëÿðíûì. Ïóñòü A = (A, Q, f, q1 , F ) êîíå÷íûé àâòîìàò, êîòîðûéäîïóñêàåò ìíîæåñòâî X , Q = {q1 , . . . , qr } è F = {qj1 , . . . , qjs }. Ïîêàæåì,÷òî ìíîæåñòâî X ðåãóëÿðíî.Çàìåòèì ñíà÷àëà, ÷òî ìíîæåñòâî F çàêëþ÷èòåëüíûõ ñîñòîÿíèé ìîæíî ñ÷èòàòü îäíîýëåìåíòíûì.
 ñàìîì äåëå, êàê âûòåêàåò èç îïðåäåëåíèÿ äîïóñòèìîãî ìíîæåñòâà, ìíîæåñòâî X åñòü îáúåäèíåíèå s ïîïàðíî40íå ïåðåñåêàþùèõñÿ ìíîæåñòâ X1 , . . . , Xs , êîòîðûå äîïóñêàþòñÿ ñîîòâåòñòâåííî àâòîìàòàìèA1 = (A, Q, f, q1 , {qj1 }), . . . , As = (A, Q, f, q1 , {qjs })(ñ÷èòàåì, ÷òî âñå ñîñòîÿíèÿ qj1 , . . . , qjs äîñòèæèìû èç íà÷àëüíîãî ñîñòîÿíèÿ q1 ).Èòàê, ïóñòü äàëåå F = {qt }, ãäå 1 6 t 6 r. Äëÿ ëþáîãî k (0 6 k 6 r)è ëþáûõ i, j (1 6 i, j 6 r) îáîçíà÷èì ÷åðåç Zijk ìíîæåñòâî âñåõ ñëîââ àëôàâèòå A, êîòîðûå ïåðåâîäÿò àâòîìàò A èç ñîñòîÿíèÿ qi â ñîñòîÿíèå qj , èñïîëüçóÿ ïðè ýòîì â êà÷åñòâå ¾ïðîìåæóòî÷íûõ¿ òîëüêî ñîñòîÿíèÿ q1 , . .
. , qk . Èíûìè ñëîâàìè, ìíîæåñòâî Zijk ñîñòîèò èç âñåõ ñëîâai1 . . . ain , äëÿ êîòîðûõ íàéäóòñÿ òàêèå ñîñòîÿíèÿ ql2 , . . . , qln èç ìíîæåñòâà{q1 , . . . , qk }, ÷òîf (ai1 , qi ) = ql2 , f (ai2 , ql2 ) = ql3 , . . . , f (ain−1 , qln−1 ) = qln , f (ain , qln ) = qj .Äàëåå ìû ïîêàæåì èíäóêöèåé ïî k , ÷òî âñå ìíîæåñòâà Zijk ðåãóëÿðíû.r= X , îòñþäà áóäåò ñëåäîâàòü ðåãóëÿðíîñòüÏîñêîëüêó, î÷åâèäíî, Z1tìíîæåñòâà X .Íà÷íåì ñ ìíîæåñòâ Zij0 . Ïî îïðåäåëåíèþ ìíîæåñòâî Zij0 ñîñòîèò èçâñåõ ñëîâ â àëôàâèòå A, êîòîðûå ïåðåâîäÿò àâòîìàò A èç ñîñòîÿíèÿ qiâ ñîñòîÿíèå qj è ïðè ýòîì íå èñïîëüçóþòñÿ íèêàêèå ¾ïðîìåæóòî÷íûå¿ñîñòîÿíèÿ.Ïóñòü i = j . Òîãäà ìíîæåñòâî Zii0 çàâåäîìî âêëþ÷àåò â ñåáÿ ïóñòîåñëîâî.
Êðîìå òîãî, åñëè åñòü áóêâû am1 , . . . , amp àëôàâèòà A, ïåðåâîäÿùèå ñîñòîÿíèå qi â ñåáÿ, òî, î÷åâèäíî, ìíîæåñòâî Zii0 ñîñòîèò èç ïóñòîãîñëîâà è ýòèõ áóêâ, ò.å. Zii0 = {Λ, am1 , . . . , amp }. Èòàê, ìíîæåñòâî Zii0 ëèáîñîñòîèò èç îäíîãî ïóñòîãî ñëîâà, ëèáî èç ñëîâ Λ, am1 , . . . , amp .  îáîèõñëó÷àÿõ ìíîæåñòâî Zii0 êîíå÷íî è ïîòîìó ðåãóëÿðíî.Ïóñòü i 6= j .
Òîãäà ìíîæåñòâî Zij0 ëèáî ïóñòî (åñëè îòñóòñòâóþò áóêâû,ïåðåâîäÿùèå ñîñòîÿíèå qi íåïîñðåäñòâåííî â ñîñòîÿíèå qj ), ëèáî ñîñòîèòèç íåêîòîðûõ áóêâ àëôàâèòà A. Ïîíÿòíî, ÷òî â îáîèõ ñëó÷àÿõ ìíîæåñòâîZij0 òàêæå ðåãóëÿðíî.Ïðåäïîëîæèì, ÷òî ðåãóëÿðíîñòü ìíîæåñòâ Zijk−1 óñòàíîâëåíà äëÿ âñåõi, j (1 6 i, j 6 r) è íåêîòîðîãî k , ãäå 1 6 k 6 r.
Äîêàæåì ðåãóëÿðíîñòüâñåõ ìíîæåñòâ Zijk .Ïóñòü ā ïðîèçâîëüíîå ñëîâî, ïðèíàäëåæàùåå ìíîæåñòâó Zijk . Òîãäàïîä äåéñòâèåì ñëîâà ā àâòîìàò A ïåðåõîäèò èç ñîñòîÿíèÿ qi â ñîñòîÿíèå qj . Åñëè ïðè ýòîì íå èñïîëüçóåòñÿ ïðîìåæóòî÷íîå ñîñòîÿíèå qk , òî41ā ∈ Zijk−1 .  ïðîòèâíîì ñëó÷àå ñëîâî ā ìîæíî ïðåäñòàâèòü â âèäå êîíêàòåíàöèè òðåõ ñëîâ ā1 , ā2 , ā3 , ãäå:1) ïîä äåéñòâèåì ñëîâà ā1 àâòîìàò A ïåðåõîäèò èç ñîñòîÿíèÿ qi âñîñòîÿíèå qk , èñïîëüçóÿ â êà÷åñòâå ïðîìåæóòî÷íûõ òîëüêî ñîñòîÿíèÿk−1);q1 , . .
. , qk−1 (ò.å. ā1 ∈ Zik2) ïîä äåéñòâèåì ñëîâà ā2 àâòîìàò A ñîâåðøàåò íåñêîëüêî öèêëè÷åñêèõ ïåðåõîäîâ èç ñîñòîÿíèÿ qk â ñåáÿ, èñïîëüçóÿ â êàæäîì öèêëå â êàk−1 ∗) );÷åñòâå ïðîìåæóòî÷íûõ òîëüêî ñîñòîÿíèÿ q1 , . . . , qk−1 (ò.å. ā2 ∈ (Zkk3) ïîä äåéñòâèåì ñëîâà ā3 àâòîìàò A ïåðåõîäèò èç ñîñòîÿíèÿ qk âñîñòîÿíèå qj , èñïîëüçóÿ â êà÷åñòâå ïðîìåæóòî÷íûõ òîëüêî ñîñòîÿíèÿk−1q1 , .
. . , qk−1 (ò.å. ā3 ∈ Zkj). èòîãå ìû ïðèõîäèì ê ôîðìóëåk−1k−1 ∗k−1Zijk = Zijk−1 ∪ Zik· (Zkk) · Zkj,k−1k−1,, Zkkêîòîðàÿ ïîêàçûâàåò, ÷òî â ñëó÷àå ðåãóëÿðíîñòè ìíîæåñòâ Zijk−1 , Zikk−1Zkj ìíîæåñòâî Zijk òàêæå áóäåò ðåãóëÿðíûì. Ýòî çàâåðøàåò äîêàçàòåëüñòâî òåîðåìû Êëèíè.ÓÏÐÀÆÍÅÍÈßÈñïîëüçóÿ îïðåäåëåíèå ðåãóëÿðíîãî ìíîæåñòâà, äîêàçàòü ðåãóëÿðíîñòü ñëåäóþùèõ ìíîæåñòâ â àëôàâèòå {a1 , a2 }:a) ëþáîå êîíå÷íîå ìíîæåñòâî ñëîâ; b) äîïîëíåíèå (äî ìíîæåñòâà {a1 , a2 }∗ )ê ëþáîìó êîíå÷íîìó ìíîæåñòâó ñëîâ; c) ìíîæåñòâî âñåõ ñëîâ, ñîñòàâëåííûõ èç ñëîâ ā1 .
. . ān ; d) ìíîæåñòâî âñåõ ñëîâ, ñîäåðæàùèõ â êà÷åñòâåïîäñëîâà çàäàííîå ñëîâî ā; e) ìíîæåñòâî âñåõ ñëîâ, êîòîðûå íå ñîäåðæàòâ êà÷åñòâå ïîäñëîâà çàäàííîå ñëîâî ā.11. Ðàññìîòðèì ñëåäóþùåå îáîáùåíèå êîíå÷íîãî àâòîìàòà. Ðàçðåøèìïåðåõîä èç îäíîãî ñîñòîÿíèÿ â ñëåäóþùåå ñîñòîÿíèå îáîáùåííîãî àâòîìàòà íå òîëüêî ïîä äåéñòâèåì áóêâ âõîäíîãî àëôàâèòà (êàê ýòî ïðåäóñìàòðèâàåòñÿ â îáû÷íîì àâòîìàòå), íî òàêæå è ïîä äåéñòâèåì ïðîèçâîëüíûõñëîâ âî âõîäíîì àëôàâèòå.
Êðîìå òîãî, ðàçðåøèì àâòîìàòó ïîä äåéñòâèåì îäíîãî è òîãî æå ñëîâà ïåðåõîäèòü â íåñêîëüêî ðàçëè÷íûõ ñîñòîÿíèé(íåäåòåðìèíèðîâàííîñòü àâòîìàòà). Òàêèì îáðàçîì, ôóíêöèÿ ïåðåõîäîâf îáîáùåííîãî àâòîìàòà A = (A, Q, f, q1 , F ) ÿâëÿåòñÿôóíêöèåé, çàäàííîé íà íåêîòîðîì êîíå÷íîì ïîäìíîæåñòâå ìíîæåñòâà A∗ × Q,êîòîðàÿ íåêîòîðûì ïàðàì (ā, qj ) ñîïîñòàâëÿåò íåïóñòûå ïîäìíîæåñòâàìíîæåñòâà Q.10.÷àñòè÷íîé42Äîêàçàòü, ÷òî âñÿêîå ìíîæåñòâî, äîïóñòèìîå òàêèì îáîáùåííûì àâòîìàòîì, ÿâëÿåòñÿ êîíå÷íî-àâòîìàòíûì.12. Îïðåäåëèì îïåðàöèþ ïîäñòàíîâêè íåñêîëüêèõ ìíîæåñòâ ñëîâ âìíîæåñòâî ñëîâ. Ïóñòü èìåþòñÿ àëôàâèòû A = {a1 , . . .
, ak } è B , ïðîèçâîëüíîå ìíîæåñòâî X ñëîâ â àëôàâèòå A è ïðîèçâîëüíûå íåïóñòûå ìíîæåñòâà Y1 , . . . , Yk ñëîâ â àëôàâèòå B . Ïîäñòàíîâêîé ìíîæåñòâ Y1 , . . . , Ykâ ìíîæåñòâî X áóäåì íàçûâàòü ìíîæåñòâî X[Y1 , . . . , Yk ] âñåõ ñëîâ â àëôàâèòå B , êîòîðûå ïîëó÷àþòñÿ ïî ñëåäóþùåìó ïðàâèëó: áåðåòñÿ ïðîèçâîëüíîå ñëîâî ai1 . . . ain èç X è â ìíîæåñòâî X[Y1 , . . . , Yk ] çàíîñÿòñÿ âñåñëîâà èç ìíîæåñòâà Yi1 · . . . · Yin . Åñëè ìíîæåñòâó X ïðèíàäëåæèò ïóñòîåñëîâî, òî ¾ïîäñòàíîâêà¿ ìíîæåñòâ Y1 , .
. . , Yk â ïóñòîå ñëîâî äàåò ïóñòîåñëîâî. Åñëè X = ∅, òî ïî îïðåäåëåíèþ ñ÷èòàåì, ÷òî X[Y1 , . . . , Yk ] = ∅.Äîêàçàòü, ÷òî ïîäñòàíîâêà êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ â êîíå÷íîàâòîìàòíîå ìíîæåñòâî äàåò êîíå÷íî-àâòîìàòíîå ìíîæåñòâî.13. Îáðàùåíèåì ñëîâà ai1 . . . ain íàçûâàåòñÿ ñëîâî ain . . . ai1 . Îáðàùåíèå ìíîæåñòâà ñëîâ X ýòî ìíîæåñòâî, ñîñòîÿùåå èç îáðàùåíèé âñåõñëîâ èç X .Äîêàçàòü, ÷òî îáðàùåíèå ëþáîãî êîíå÷íî-àâòîìàòíîãî ìíîæåñòâà ÿâëÿåòñÿ êîíå÷íî-àâòîìàòíûì ìíîæåñòâîì.43Ãëàâà 3ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ-ÏÐÅÎÁÐÀÇÎÂÀÒÅËÈ 1. Êîíå÷íûé àâòîìàò ñ âûõîäîì. Òåîðåìà ÌóðàÐàñøèðèì ïîíÿòèå êîíå÷íîãî àâòîìàòà. Ïóñòü A = {a1 , .
. . , ak }, B ={b1 , . . . , bm } êîíå÷íûå àëôàâèòû. Ìû õîòèì îïðåäåëèòü êîíå÷íûé àâòîìàò ñ âõîäíûì àëôàâèòîì A è âûõîäíûì àëôàâèòîì B òàê, ÷òîáûîí ìîã âû÷èñëÿòü ñëîâàðíóþ ôóíêöèþ âèäà A∗ → B ∗ , ò.å. îòîáðàæåíèåìíîæåñòâà A∗ âñåõ ñëîâ â àëôàâèòå A â ìíîæåñòâî B ∗ âñåõ ñëîâ â àëôàâèòå B . Äëÿ ðåàëèçàöèè ýòîãî íàìåðåíèÿ ïðîùå âñåãî ñíàáäèòü àâòîìàòáåç âûõîäà òàê íàçûâàåìîé, êîòîðàÿ íà êàæäîì øàãåðàáîòû àâòîìàòà âûäàåò íåêîòîðóþ áóêâó âûõîäíîãî àëôàâèòà B . Îòìåòèì, ÷òî â êîíöåïöèè àâòîìàòà ñ âûõîäîì çàêëþ÷èòåëüíûå ñîñòîÿíèÿíå ïðåäóñìîòðåíû.Èòàê, êîíå÷íûé àâòîìàò A ñ âûõîäîì çàäàåòñÿ íàáîðîì (A, B, Q, f,g, q1 ), ãäå A âõîäíîé, B âûõîäíîé àëôàâèòû àâòîìàòà, Q = {q1 , .
. . ,qr } ìíîæåñòâî ñîñòîÿíèé, f ôóíêöèÿ ïåðåõîäîâ, îòîáðàæàþùàÿìíîæåñòâî A × Q â ìíîæåñòâî Q, g ôóíêöèÿ âûõîäîâ, îòîáðàæàþùàÿìíîæåñòâî A × Q â ìíîæåñòâî B , q1 íà÷àëüíîå ñîñòîÿíèå àâòîìàòà A.Ñ÷èòàåì, ÷òî àâòîìàò A ïðåîáðàçóåò (ïåðåâîäèò) ñëîâî ai1 . . . ain âàëôàâèòå A â ñîîòâåòñòâóþùåå ñëîâî bj1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
