С.С. Марченков - Избранные главы дискретной математики (1124120), страница 8
Текст из файла (страница 8)
. , qlu (îòìåòèì, ÷òî ìíîæåñòâà {qk1 , . . . , qkt },. . . , {ql1 , . . . , qlu } ìîãóò ïåðåñåêàòüñÿ). Âîîáùå, åñëè àâòîìàò A ïîä äåéñòâèåì ñëîâà ai1 . . . aid (ãäå d < n) ìîæåò ïåðåéòè â ñîñòîÿíèå qj èf (aid+1 , qj ) = {qm1 , . . . , qmv },òî ïîä äåéñòâèåì ñëîâà ai1 . . . , aid aid+1 àâòîìàò A ìîæåò ïåðåéòè â ëþáîåèç ñîñòîÿíèé qm1 , . . .
, qmv .Ñ÷èòàåì, ÷òî àâòîìàò Añëîâî ā, åñëè ïîä äåéñòâèåì ñëîâàā àâòîìàò A ìîæåò ïîïàñòü õîòÿ áû â îäíî èç ñîñòîÿíèé ìíîæåñòâàF . Òàê æå, êàê è âûøå, ÷åðåç D(A) îáîçíà÷àåì ìíîæåñòâî âñåõ ñëîâ,äîïóñêàåìûõ àâòîìàòîì A.äîïóñêàåòÊëàññ ìíîæåñòâ, äîïóñêàåìûõ êîíå÷íûìè íåäåòåðìèíèðîâàííûìè àâòîìàòàìè, ñîâïàäàåò ñ êëàññîì êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ.Òåîðåìà 2.4. îäíó ñòîðîíó óòâåðæäåíèå òåîðåìû î÷åâèäíî:âñÿêèé êîíå÷íûé àâòîìàò ìîæíî ñ÷èòàòü íåäåòåðìèíèðîâàííûì àâòîìàòîì è ïîòîìó âñÿêîå êîíå÷íî-àâòîìàòíîå ìíîæåñòâî äîïóñêàåòñÿ òàêæåè íåäåòåðìèíèðîâàííûì àâòîìàòîì. Äîêàæåì óòâåðæäåíèå òåîðåìû âäðóãóþ ñòîðîíó.Ïóñòü A = (A, Q, f, q1 , F ) íåäåòåðìèíèðîâàííûé àâòîìàò è ìíîæåñòâî Q ñîñòîèò èç r ñîñòîÿíèé.
Ïîñòðîèì ïî íåìó îáû÷íûé (äåòåðìèíèðîâàííûé) àâòîìàò A0 , êîòîðûé äîïóñêàåò òî æå ñàìîå ìíîæåñòâî D(A).Èç àíàëèçà äåéñòâèÿ ñëîâà (èç A∗ ) íà íåäåòåðìèíèðîâàííûé àâòîìàò Aâèäíî, ÷òî â ïðèíöèïå ëþáîå íåïóñòîå ïîäìíîæåñòâî ìíîæåñòâà Q ìîæåò ÿâëÿòüñÿ ìíîæåñòâîì òåõ ñîñòîÿíèé, â êàæäîå èç êîòîðûõ àâòîìàòÄîêàçàòåëüñòâî.35A ïîïàäàåò ïîä äåéñòâèåì îäíîãî è òîãî æå âõîäíîãî ñëîâà. Ïîýòîìó âêà÷åñòâå ñîñòîÿíèé àâòîìàòà A0 âîçüìåì âñå íåïóñòûå ïîäíîæåñòâà ìíîæåñòâà Q. ×èñëî òàêèõ ïîäìíîæåñòâ åñòü r0 = 2r − 1.
Îáîçíà÷èì ýòèìíîæåñòâà-ñîñòîÿíèÿ àâòîìàòà A0 ÷åðåç q10 , . . . , qr0 0 .Äîâîëüíî ïîíÿòíî, êàê îïðåäåëèòü ôóíêöèþ ïåðåõîäîâ f 0 àâòîìàòàA0 : åñëè qj0 = {qj1 , . . . , qjs }, òî, ñ÷èòàÿ çíà÷åíèÿ f (ai , qj1 ), . . . , f (ai , qjs )ïîäìíîæåñòâàìè ìíîæåñòâà Q, ïîëîæèìf 0 (ai , qj0 ) = ql0 ,ãäå ql0 = f (ai , qj1 ) ∪ .
. . ∪ f (ai , qjs ).Ñîîòâåòñòâåííî, ìíîæåñòâî F 0 àâòîìàòà A0 áóäåò ñîñòîÿòü èç âñåõ ïîäìíîæåñòâ ìíîæåñòâà Q, êîòîðûå èìåþò õîòÿ áû îäèí îáùèé ýëåìåíò ñìíîæåñòâîì F . Íà÷àëüíûì ñîñòîÿíèåì àâòîìàòà A0 ÿâëÿåòñÿ îäíîýëåìåíòíîå ìíîæåñòâî {q1 }.Òàêèì îáðàçîì, äëÿ ïðîèçâîëüíîãî ñëîâà ā â àëôàâèòå A àâòîìàò0A , íà÷èíàÿ ñ îäíîýëåìåíòíîãî ìíîæåñòâà {q1 }, ïîä äåéñòâèåì ñëîâà āäîñòèãàåò ñîñòîÿíèÿ {qj1 , . . . , qjs } òîãäà è òîëüêî òîãäà, êîãäà àâòîìàò Aïîä äåéñòâèåì ñëîâà ā ìîæåò ïîïàñòü â ëþáîå èç ñîñòîÿíèé qj1 , .
. . , qjs .Îòñþäà ñðàçó ñëåäóåò, ÷òî D(A0 ) = D(A). Òåîðåìà äîêàçàíà.ÓÏÐÀÆÍÅÍÈßÎáîáùèì ïîíÿòèå íåäåòåðìèíèðîâàííîãî àâòîìàòà â äâóõ íàïðàâëåíèÿõ. Âî-ïåðâûõ, ðàçðåøèì àâòîìàòó âìåñòî îäíîãî íà÷àëüíîãî ñîñòîÿíèÿ èìåòü íåñêîëüêî íà÷àëüíûõ ñîñòîÿíèé. Ïðè ýòîì ìíîæåñòâî,äîïóñòèìîå àâòîìàòîì, áóäåò ñîñòîÿòü èç âñåõ ñëîâ, ïîä äåéñòâèåì êîòîðûõ àâòîìàò èç êàêîãî-ëèáî íà÷àëüíîãî ñîñòîÿíèÿ ïåðåõîäèò â êàêîåëèáî çàêëþ÷èòåëüíîå ñîñòîÿíèå. Âî-âòîðûõ, íå áóäåì òðåáîâàòü, ÷òîáûäëÿ ëþáîé áóêâû ai âõîäíîãî àëôàâèòà è ëþáîãî ñîñòîÿíèÿ qj çíà÷åíèåf (ai , qj ) áûëî îïðåäåëåíî (â äèàãðàììå Ìóðà òàêîãî àâòîìàòà íå èç âñÿêîãî ñîñòîÿíèÿ qj âûõîäèò äóãà, ïîìå÷åííàÿ áóêâîé ai ).
Íàçîâåì òàêèåîáîáùåííûå íåäåòåðìèíèðîâàííûå àâòîìàòû.Äîêàçàòü, ÷òî âñÿêîå ìíîæåñòâî, äîïóñòèìîå èñòî÷íèêîì, ÿâëÿåòñÿêîíå÷íî-àâòîìàòíûì.7.èñòî÷íèêàìè 4. Îïåðàöèè ïðîèçâåäåíèÿ è èòåðàöèè 1 ìû îïðåäåëèëè îïåðàöèþ êîíêàòåíàöèè ñëîâ. Íåòðóäíî âèäåòü,÷òî îïåðàöèÿ êîíêàòåíàöèè àññîöèàòèâíà, íî íå êîììóòàòèâíà.
Ïî ñó36ùåñòâó êîíêàòåíàöèÿ ÿâëÿåòñÿ (íåêîììóòàòèâíîé) îïåðàöèåé óìíîæåíèÿ ñëîâ. Íà îñíîâå îïåðàöèè êîíêàòåíàöèè äàäèì îïðåäåëåíèå îïåðàöèèïðîèçâåäåíèÿ ìíîæåñòâ, ñîñòîÿùèõ èç ñëîâ.Ïóñòü X, Y ïðîèçâîëüíûå íåïóñòûå ìíîæåñòâà ñëîâ.ìíîæåñòâ X, Y íàçûâàåòñÿ ìíîæåñòâî X · Y âñåõ ñëîâ âèäà āb̄, ãäå ā ∈ Xè b̄ ∈ Y . Èíà÷å ãîâîðÿ,Ïðîèçâåäåíèåì[X ·Y =āb̄.ā∈X, b̄∈YÏîñêîëüêó â îñíîâå îïåðàöèè ïðîèçâåäåíèÿ ëåæèò îïåðàöèÿ êîíêàòåíàöèè, îïåðàöèÿ ïðîèçâåäåíèÿ òàêæå áóäåò àññîöèàòèâíîé, íî íå êîììóòàòèâíîé îïåðàöèåé.
Åñëè n > 1, òî âìåñòî X · X · . . . · X (n ðàç),êàê îáû÷íî, áóäåì ïèñàòü X n . Óäîáíî ñ÷èòàòü, ÷òî äëÿ ëþáîãî íåïóñòîãî ìíîæåñòâà X ìíîæåñòâî X 0 îïðåäåëåíî è ñîñòîèò èç îäíîãî ïóñòîãîñëîâà. Îòìåòèì òàêæå, ÷òî äëÿ ëþáîãî ìíîæåñòâà X ñïðàâåäëèâû ðàâåíñòâà ∅ · X = X · ∅ = ∅.Îïåðàöèÿ áîëåå ñëîæíàÿ îïåðàöèÿ, êîòîðàÿ îñíîâàíà íàîïåðàöèÿõ ïðîèçâåäåíèÿ è îáúåäèíåíèÿ. Èìåííî, åñëè X íåïóñòîå ìíîæåñòâî ñëîâ, òîX ∗ ìíîæåñòâà X íàçûâàåòñÿ áåñêîíå÷íîå îáúåäèíåíèåèòåðàöèèèòåðàöèåéX0 ∪ X1 ∪ X2 ∪ .
. . ∪ Xn ∪ . . . .Èíà÷å ãîâîðÿ, ñëîâî ā ïðèíàäëåæèò ìíîæåñòâó X ∗ â òîì è òîëüêî òîìñëó÷àå, êîãäà ëèáî ā = Λ, ëèáî ñóùåñòâóþò òàêèå ñëîâà ā1 , . . . , ān èç X(çäåñü n òàêæå ÿâëÿåòñÿ ïàðàìåòðîì), ÷òî ā = ā1 . . . ān . Çàìåòèì, ÷òîåñëè â ìíîæåñòâî X âõîäèò íåïóñòîå ñëîâî ā, òî ìíîæåñòâó X ∗ ïðèíàäëåæàò âñå ñëîâà ā, ā2 , ā3 , . . ., ò.å. ìíîæåñòâî X ∗ ÿâëÿåòñÿ áåñêîíå÷íûì.Íàïðîòèâ, åñëè X = {Λ}, òî X ∗ = {Λ}. Èòåðàöèÿ ïóñòîãî ìíîæåñòâà ïîîïðåäåëåíèþ åñòü ïóñòîå ìíîæåñòâî.Îáðàòèì âíèìàíèå íà òî, ÷òî ìíîæåñòâî A∗ âñåõ ñëîâ â àëôàâèòå A(âêëþ÷àÿ ïóñòîå ñëîâî) äåéñòâèòåëüíî åñòü èòåðàöèÿ ìíîæåñòâà A.Öåëü ýòîãî ïàðàãðàôà ïîêàçàòü, ÷òî îïåðàöèè ïðîèçâåäåíèÿ è èòåðàöèè íå âûâîäÿò çà ïðåäåëû êëàññà êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ.Îïåðàöèÿ ïðîèçâåäåíèÿ ñîõðàíÿåò êîíå÷íóþ àâòîìàòíîñòü ìíîæåñòâ.Òåîðåìà 2.5.Ïóñòü A = (A, Q, f, q1 , F ), B = (A, Q0 , f 0 , q10 , F 0 ) êîíå÷íûå àâòîìàòû è X = D(A), Y = D(B).
Ïîñòðîèì àâòîìàò C ,êîòîðûé äîïóñêàåò ìíîæåñòâî X · Y .Äîêàçàòåëüñòâî.37Èñõîäÿ èç îïðåäåëåíèÿ ìíîæåñòâà X · Y , ïîïûòàåìñÿ â ïîñòðîåíèèàâòîìàòà C ðåàëèçîâàòü ñëåäóþùóþ èäåþ: êàæäîå çàêëþ÷èòåëüíîå ñîñòîÿíèå àâòîìàòà A â àâòîìàòå C áóäåò îäíîâðåìåííî ¾ðàññìàòðèâàòüñÿ¿è êàê íà÷àëüíîå ñîñòîÿíèå àâòîìàòà B . Ñðàçó ÿñíî, ÷òî èñêîìûé àâòîìàòC , ðåàëèçóþùèé ýòó èäåþ, äîëæåí áûòü íåäåòåðìèíèðîâàííûì àâòîìàòîì. Îäíàêî ýòî íå ìîæåò ñëóæèòü ïðåïÿòñòâèåì íà ïóòè âûïîëíåíèÿçàäóìàííîãî ïëàíà, ïîñêîëüêó â ïðåäûäóùåì ïàðàãðàôå óêàçàí ñïîñîá¾äåòåðìèíèçàöèè¿ íåäåòåðìèíèðîâàííîãî àâòîìàòà.Îïðåäåëèì áîëåå ïîäðîáíî àâòîìàò C . Áóäåì ñ÷èòàòü, ÷òî ìíîæåñòâàQ è Q0 íå ïåðåñåêàþòñÿ. Ìíîæåñòâî ñîñòîÿíèé àâòîìàòà C áóäåò ïðåäñòàâëÿòü ñîáîé îáúåäèíåíèå Q∪Q0 .
Îïðåäåëèì ôóíêöèþ ïåðåõîäîâ h àâòîìàòà C . Ïóñòü q ∈ Q ∪ Q0 . Åñëè q ∈/ F ëèáî q ∈ Q0 , òî çíà÷åíèå h(ai , q)ñîâïàäàåò ñ ñîîòâåòñòâóþùèì çíà÷åíèåì f (ai , q) èëè f 0 (ai , q). Åñëè æåq ∈ F , òî ôóíêöèÿ h íà íàáîðå (ai , q) ïðèíèìàåò äâà çíà÷åíèÿ f (ai , q)è f 0 (ai , q10 ).
Òàêèì îáðàçîì, íåäåòåðìèíèðîâàííîñòü àâòîìàòà C ïðîÿâëÿåòñÿ òîëüêî â ñîñòîÿíèÿõ q èç ìíîæåñòâà F : â íèõ àâòîìàò C ìîæåòïðîäîëæàòü ðàáîòàòü êàê àâòîìàò A, ëèáî íà÷àòü ðàáîòàòü êàê àâòîìàòB.Çàêëþ÷èòåëüíûìè ñîñòîÿíèÿìè àâòîìàòà C îáúÿâèì âñå ñîñòîÿíèÿ èçìíîæåñòâà F 0 . Íåòðóäíî âèäåòü ÷òî àâòîìàò C äåéñòâèòåëüíî äîïóñêàåòìíîæåñòâî X · Y .
Òåîðåìà äîêàçàíà.Îïåðàöèÿ èòåðàöèè ñîõðàíÿåò êîíå÷íóþ àâòîìàòíîñòü ìíîæåñòâ.Òåîðåìà 2.6.Ïóñòü A = (A, Q, f, q1 , F ) êîíå÷íûé àâòîìàò èX = D(A). Åñëè X = {Λ}, òî X ∗ = {Λ} è àâòîìàò A äîïóñêàåò ìíîæåñòâî X ∗ . Ïðåäïîëîæèì äàëåå, ÷òî ìíîæåñòâî X ñîäåðæèò õîòÿ áû îäíîíåïóñòîå ñëîâî. Ïî àâòîìàòó A áóäåì ñòðîèòü íåäåòåðìèíèðîâàííûé àâòîìàò C , êîòîðûé äîïóñêàåò ìíîæåñòâî X ∗ . Îáðàùàÿñü ê îïðåäåëåíèþìíîæåñòâà X ∗ , âèäèì, ÷òî àâòîìàò C ìîã áû ïîëó÷èòüñÿ èç àâòîìàòàA, åñëè â àâòîìàòå A ¾îòîæäåñòâèòü¿ âñå çàêëþ÷èòåëüíûå ñîñòîÿíèÿ ñíà÷àëüíûì ñîñòîÿíèåì q1 .Áîëåå ôîðìàëüíî: ñëåäóþùèì îáðàçîì ðàñøèðèì ôóíêöèþ ïåðåõîäîâf àâòîìàòà A äî ôóíêöèè f 0 àâòîìàòà C : åñëè ñîñòîÿíèå qj âõîäèò âìíîæåñòâî F , òî ïóñòü äëÿ ëþáîé áóêâû ai èç A çíà÷åíèåì f 0 (ai , qj ) áóäóòñîñòîÿíèÿ f (ai , qj ) è f (ai , q1 ) (ìîæåò ñòàòüñÿ, ÷òî f (ai , qj ) = f (ai , q1 ),òîãäà ôóíêöèÿ f 0 ïðèíèìàåò íà íàáîðå (ai , qj ) îäíî çíà÷åíèå f (ai , qj )).Íà÷àëüíîå ñîñòîÿíèå q1 è ìíîæåñòâî çàêëþ÷èòåëüíûõ ñîñòîÿíèé F ìûÄîêàçàòåëüñòâî.38îñòàâëÿåì äëÿ àâòîìàòà C áåç èçìåíåíèé.Ëåãêî ïîíÿòü, êàê áóäåò ðàáîòàòü àâòîìàò C ïðè ïîäà÷å íà åãî âõîäïðîèçâîëüíîãî ñëîâà.
Äî òîãî ìîìåíòà, ïîêà àâòîìàò C íå ïîïàäåò â îäíî èç ñîñòîÿíèé ìíîæåñòâà F , îí áóäåò äåéñòâîâàòü òî÷íî òàê æå, êàêàâòîìàò A. Ïðè ïîïàäàíèè â ñîñòîÿíèå ìíîæåñòâà F ïåðåä àâòîìàòîìC âîçíèêàåò àëüòåðíàòèâà: ëèáî ïðîäîëæàòü äåéñòâîâàòü êàê àâòîìàò A(ò.å. âîñïîëüçîâàòüñÿ ïåðåõîäîì f (ai , qj )), ëèáî ïðèíÿòü äàííîå çàêëþ÷èòåëüíîå ñîñòîÿíèå çà íà÷àëüíîå ñîñòîÿíèå àâòîìàòà A è â ñîîòâåòñòâèè ñýòèì äåéñòâîâàòü êàê àâòîìàò A, êîòîðûé íàõîäèòñÿ â ñîñòîÿíèè q1 (ò.å.èñïîëüçîâàòü ïåðåõîä f (ai , q1 )). Ðàçóìååòñÿ, ïîäîáíûå àëüòåðíàòèâû äëÿðàññìàòðèâàåìîãî âõîäíîãî ñëîâà ìîãóò âîçíèêàòü íå îäèí ðàç.Òàêèì îáðàçîì, âñÿêîå ñëîâî, äîïóñêàåìîå àâòîìàòîì C , ïðåäñòàâëÿåòñîáîé ïðîèçâåäåíèå íåñêîëüêèõ ñëîâ, äîïóñêàåìûõ àâòîìàòîì A.
Âåðíîè îáðàòíîå: âñÿêîå ñëîâî, ïðåäñòàâèìîå â âèäå ïðîèçâåäåíèÿ íåñêîëüêèõñëîâ, äîïóñêàåìûõ àâòîìàòîì A, äîïóñêàåòñÿ àâòîìàòîì C . Çíà÷èò, D(C)ñîâïàäàåò ñ ìíîæåñòâîìX1 ∪ X2 ∪ . . . ∪ Xn ∪ . . .(2.3)Åñëè Λ ∈ X , òî ìíîæåñòâî (2.3) ðàâíî ìíîæåñòâó X ∗ .  ïðîòèâíîì ñëó÷àå, ÷òîáû ïîëó÷èòü ìíîæåñòâî X ∗ , íåîáõîäèìî ê ìíîæåñòâó (2.3) äîáàâèòü ïóñòîå ñëîâî. Îäíàêî íàì èçâåñòíî, ÷òî îäíîýëåìåíòíîå ìíîæåñòâî{Λ} ÿâëÿåòñÿ êîíå÷íî-àâòîìàòíûì. Ïðèìåíÿÿ òåïåðü ïîñëåäîâàòåëüíîòåîðåìó 2.4 ê ìíîæåñòâó D(C) è òåîðåìó 2.3 ê ìíîæåñòâàì D(C) è {Λ},ïîëó÷àåì êîíå÷íóþ àâòîìàòíîñòü ìíîæåñòâà X ∗ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
