1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 10
Текст из файла (страница 10)
Îäèí èç âîçìîæíûõ ñïîñîáîâ, êîòîðûé ìû ñåé÷àñîïèøåì, îñíîâàí íà òàê íàçûâàåìûõ êîíâîëþöèÿõ. ÏóñòüA íåêîòî-ðûé êîíå÷íûé àëôàâèò, è ïóñòü ♦ íåêîòîðûé ñèìâîë, íå ïðèíàäëåæàùèé A. Îáîçíà÷èìA[k] êîíå÷íûé àëôàâèò, ñîñòîÿùèé èç ìàòðèö ÷åðåça1ñòîëáöîâ âèäà..., a1 , . . . , ak ∈ A ∪ {♦},ðàññìàòðèâàåìûõ êàê ñèì-akâîëû íåêîòîðîãî íîâîãî àëôàâèòà.α1 , .
. . , αk ñëîâà íàä àëôàâèòîì A. Èõ êîíâîëþöèåé íàçîâ¼ì♦[k]ñëîâî â àëôàâèòå A , îáîçíà÷àåìîå ÷åðåç (α1 , . . . , αk ) , êîòîðîå îáðàçóåòñÿ ñëåäóþùèì îáðàçîì. Ïóñòü m = max{|α1 |, . . . , |αk |}. Äëÿ êàæäîãî0m−|αi |ñëîâà αi , i = 1, .
. . , k îáîçíà÷èì ÷åðåç αi ñëîâî αi ♦. Òàêèì îáðàçîì,0âñå ñëîâà αi , i = 1, . . . , k èìåþò îäèíàêîâóþ äëèíó m. Âûïèøåì ñëîâàαi0 , i = 1, . . . , k äðóã íàä äðóãîì, âûðîâíÿâ çàïèñè ïî ëåâîìó êðàþ. Óíàñ ïîëó÷èòñÿ ìàòðèöà èç ñèìâîëîâ àëôàâèòà A ∪ {♦}. ż ñòîëáöû, ðàñ[k]ñìàòðèâàåìûå, êàê ñèìâîëû àëôàâèòà A , è áóäóò îáðàçîâûâàòü ñëîâî(α1 , . .
. , αk )♦ â àëôàâèòå A[k] . ab♦Íàïðèìåð, êîíâîëþöèåé ñëîâ ab, c è def áóäåò ñëîâî c ♦ ♦ def[3]íàä àëôàâèòîì A .∗ nÌíîæåñòâî S ⊆ (A ) , n > 0 íàçûâàåòñÿ àâòîìàòíûì, åñëè àâòîìàò♦♦íûì ÿâëÿåòñÿ ìíîæåñòâî S = {ᾱ | ᾱ ∈ S}.Óïðàæíåíèå. Äîêàæèòå, ÷òî îòíîøåíèå ðàâåíñòâà íà A∗ àâòîìàòíî.ÏóñòüÒåïåðü ìû ìîæåì äàòü òî÷íîå îïðåäåëåíèå àâòîìàòíûõ ñòðóêòóð.Âåçäå íèæå ìû áóäåì ðàññìàòðèâàòü òîëüêî ïðåäèêàòíûå ñèãíàòóðû.Ýòî îãðàíè÷åíèå íå ñëèøêîì îáðåìåíèòåëüíî, òàê êàê âñÿêóþ îïåðàöèþ3.1.
Êîíâîëþöèè è îïðåäåëåíèå àâòîìàòíûõ ìîäåëåéf (x1 , . . . , xn )ìîæíî çàìåíèòü íà îòíîøåíèåPf ,63êîòîðîå ÿâëÿåòñÿ å¼ ãðà-ôèêîì, ò.å.,Pf = {hx1 , . . . , xn , yi | f (x1 , . . . , xn ) = y};òàêèì îáðàçîì, ìû äëÿ óäîáñòâà ìîæåì ïîçâîëèòü ñåáå èñïîëüçîâàíèåçàïèñèf (x1 , . . .
, xn ) = y ,ïîäðàçóìåâàÿ ïîä íåé çàïèñüPf (x1 , . . . , xn , y).mk−1 íàçûâàåòñÿ àâòîÑòðóêòóðà A; P0m0 , . . . , Pk−1ìàòíîé, åñëè A àâòîìàòíûé ÿçûê è âñå ìíîæåñòâà Pi♦ , i < ω , àâòîìàòíû.Îïðåäåëåíèå 3.1.1Åñëè íåêîòîðàÿ ñòðóêòóðàòî áóäåì ãîâîðèòü, ÷òîA.BAB,àâòîìàòíûì ïðåäñòàâëåíèåì äëÿèçîìîðôíà àâòîìàòíîé ñòðóêòóðåÿâëÿåòñÿÅñëè ó ñòðóêòóðû ñóùåñòâóåò àâòîìàòíîå ïðåäñòàâëåíèå, òî áóäåìíàçûâàòü å¼àâòîìàòíî ïðåäñòàâèìîé.Ïðèâåä¼ì íåêîòîðûå ïðèìåðû àâòîìàòíûõ ñòðóêòóð.Ïðèìåð 1. Ñòðóêòóðû ñ îäíîìåñòíûìè ïðåäèêàòàìè.Ëþáàÿ íå áî-ëåå, ÷åì ñ÷¼òíàÿ ñòðóêòóðà, ñèãíàòóðà êîòîðîé ñîñòîèò èç îäíîìåñòíûõ ïðåäèêàòîâ, èìååò àâòîìàòíîå ïðåäñòàâëåíèå.
 ñàìîì äåëå, ïóñòüA = hA; P0 , . . . , Pk−1 i òàêàÿ ñòðóêòóðà. Ðàññìîòðèì ïðåäèêàòû P ε , ãäåεïðîáåãàåò ìíîæåñòâî âñåõ îòîáðàæåíèé èç{0, . . . , k − 1}â{0, 1},îïðå-äåë¼ííûõ, êàê(ε(0)P ε = P0ÏðåäèêàòûìíîæåñòâîA,ε(1)∩ P1Pεε(k−1)∩ · · · ∩ Pk−1,ãäåPij =Pi ,åñëè¬Pi ,j=1åñëèj = 0.ïîïàðíî íå ïåðåñåêàþòñÿ, â îáúåäèíåíèè äàþò âñ¼è ëþáîé èç ïðåäèêàòîâäÿùåãî ìíîæåñòâà ïðåäèêàòîâ âèäàPPiεÿâëÿåòñÿ îáúåäèíåíèåì ïîäõî-. Ïîñêîëüêó îáúåäèíåíèå êîíå÷-íîãî ÷èñëà àâòîìàòíûõ ïðåäèêàòîâ àâòîìàòíî, äëÿ äîêàçàòåëüñòâà ñóùåñòâîâàíèÿ àâòîìàòíîé êîïèè íàøåé ñòðóêòóðû äîñòàòî÷íî ïîêàçàòü,÷òî ëþáàÿ òàêàÿ ñòðóêòóðà ñ îäíîìåñòíûìè ïîïàðíî íåïåðåñåêàþùèìèñÿ ïðåäèêàòàìè, äàþùèìè â îáúåäèíåíèè âñ¼ îñíîâíîå ìíîæåñòâî, èìååò àâòîìàòíîå ïðåäñòàâëåíèå.
Íàø àëôàâèò áóäåò ñîñòîÿòü èç ñèìâîëîâa0 , a1 , . . . , ak−1 , b.Pi êîíå÷íîå ìíîæåñòâî, òî åãî ìîæíî ïðåäñòàmâèòü â âèäå êîíå÷íîãî àâòîìàòíîãî ÿçûêà {ai , ai b, . . . , ai b }, äëÿ ïîäõîäÿùåãîm.ÅñëèÅñëè æå îíî áåñêîíå÷íî, òî åãî ìîæíî ïðåäñòàâèòü â âèäå∗ðåãóëÿðíîãî ÿçûêà ñ êîäîì ai b . Âçÿâ â êà÷åñòâå îñíîâíîãî ìíîæåñòâàÃëàâà 3. Àâòîìàòíûå ñòðóêòóðû64îáúåäèíåíèå òàê ïîëó÷åííûõ ÿçûêîâ, ìû ïîëó÷èì òðåáóåìîå ïðåäñòàâëåíèå.Ïðèìåð 2.
Ñ÷¼òíûé ïëîòíûé ïîðÿäîê áåç êîíöîâ. Õîðîøî èçâåñòíî, ÷òîëþáûå äâà ñ÷åòíûõ ëèíåéíûõ ïîðÿäêà, íå èìåþùèõ íè íàèìåíüøåãî íèíàèáîëüøåãî ýëåìåíòà è îáëàäàþùèå ñâîéñòâîì ïëîòíîñòè (ò.å., òàêèå,÷òî äëÿ ëþáûõx< yíàéä¼òñÿzñî ñâîéñòâîìx < y < z)èçîìîðôíûìåæäó ñîáîé. Ïîêàæåì, êàê ïîñòðîèòü àâòîìàòíîå ïðåäñòàâëåíèå òàêîãî ïîðÿäêà.
Îñíîâíûì ìíîæåñòâîì íàøåé ñòðóêòóðû áóäåò àâòîìàòíîå∗ìíîæåñòâî A = {0, 1} {1}. Çàäàäèì íà í¼ì ëåêñèêîãðàôè÷åñêèé ïîðÿäîê. ×èòàòåëþ ïðåäëàãàåòñÿ â êà÷åñòâå óïðàæíåíèÿ ïîêàçàòü, ÷òî ëåêñèêîãðàôè÷åñêèé ïîðÿäîê íà ñëîâàõ ëþáîãî êîíå÷íîãî àëôàâèòà àâòîìàòåí. Îñòàëîñü ïîêàçàòü, ÷òî òàêîé ïîðÿäîê ÿâëÿåòñÿ ïëîòíûì è íåèìååò êîíöåâûõ ýëåìåíòîâ.  ñàìîì äåëå, äëÿ ëþáîãî ñëîâà α1 èìååì:α01 <lex α1 <lex α11, ò.å., α1 íå ÿâëÿåòñÿ íè íàèìåíüøèì íè íàèáîëüøèìýëåìåíòîì.[ÏÐÅÄËÎÆÅÍÈÅ: Ìîæíî óòî÷íèòü, ÷òî ëåêñèêî-ãðàôè÷åñêèé ïîðÿäîê ðàññìàòðèâàåòñÿ â ïðèìåðå äëÿ íåïóñòûõñëîâ êîíå÷íîãî àëôàâèòà.] Ïðîâåðèì ïëîòíîñòü. Ïóñòüα1 <lex β1.Òîãäà âîçìîæíû äâà ñëó÷àÿ:Ñëó÷àé 1. Ñëîâî α1 ÿâëÿåòñÿ ñîáñòâåííûì íà÷àëüíûì ñåãìåíòîì ñëîâàβ1.Òîãäà äëÿ ïîäõîäÿùåãî β1 âûïîëíåíî β1 = α1β1 1, è ìû èìååì:α1 <lex α1β01 <lex α1β1 1 = β1,ò.å., ñòðîãî ìåæäóα1èβ1íàõîäèòñÿ åù¼ îäíî ñëîâîα1β01èçA.Ñëó÷àé 2.
Íåðàâåíñòâî α1 <lex β1 ìîæíî ïðåäñòàâèòü â âèäåα1 = α0 0γ <lex α0 1δ = β1.Òîãäàα1 = α0 0γ <lex α0 0γ1 <lex α0 1δ = β1,è ìû ñíîâà ïîëó÷èì ñëîâî, íàõîäÿùååñÿ ñòðîãî ìåæäóα1èβ1.Òàêèì îáðàçîì, íàø ïîðÿäîê îáëàäàåò ñâîéñòâîì ïëîòíîñòè.3.2. Ñâîéñòâà êîíâîëþöèé è çàìå÷àòåëüíûå ñâîéñòâà àâòîìàòíûõ ñòðóêòóð653.2Ñâîéñòâà êîíâîëþöèé è çàìå÷àòåëüíûåñâîéñòâà àâòîìàòíûõ ñòðóêòóðÏðåæäå, ÷åì äîêàçàòü íåêîòîðûå çàìå÷àòåëüíûå ñâîéñòâà àâòîìàòíûõìîäåëåé, ìû äîêàæåì íåñêîëüêî îáùèõ ïðåäëîæåíèé î êîíâîëþöèÿõ.Îïðåäåëèì ïîíÿòèåÏóñòü çàäàíû àâòîìàòûäåêàðòîâà ïðîèçâåäåíèÿ êîíå÷íûõ àâòîìàòîâ.Ai = hQi , Ai , qi , ti , Fi i, i = 0, 1. Îïðåäåëèì àâòî-ìàòA0 × A1 = hQ, A, q, t, F i ,â êîòîðîìQ = Q0 × Q1 ,a0 a ∈ Ai , i ∈ {0, 1} ,A =a1 iq0,q =q1t(s0 , a0 )a0=,t hs0 , s1 i ,a1t(s1 , a1 )F = F0 × F1 .A0 × A1òîâ A0 è A1 .Àâòîìàòáóäåò íàçûâàòüñÿÈç îïðåäåëåíèÿ àâòîìàòàäåêàðòîâûì ïðîèçâåäåíèåì àâòîìà-A0 × A1ñëåäóåò, ÷òî åñëè âäîëü íåêîòîðîãîïóòè èç íà÷àëüíîãî ñîñòîÿíèÿ ïî ýòîìó àâòîìàòó ÷èòàåòñÿ ñëîâîa0b0a1b1···ak−1bk−1,A0 , ïðîõîäÿùåãî ïî ïåðâûì êîîðäèíàòàì ýòîãî ïóòè ÷èòàåòñÿ ñëîâî a0 a1 · · · ak−1 , à âäîëü ïóòè ïî A1 , ïðîõîäÿùåãî ïîâòîðûì êîîðäèíàòàì ñëîâî b0 b1 · · · bk−1 .
Ñ ó÷¼òîì îïðåäåëåíèÿ íà÷àëüíîãî è êîíå÷íûõ ñîñòîÿíèé àâòîìàòà A0 × A1 , ìû ïîëó÷àåì ñëåäóþùååòî âäîëü ïóòè ïî àâòîìàòóïðåäëîæåíèå:Ïðåäëîæåíèå 3.2.1L(A0 × A1 ) = {hα, βi ∈ L(A0 ) × L(A1 ) | |α| = |β|}♦ .Ãëàâà 3. Àâòîìàòíûå ñòðóêòóðû66Ïóñòü A0 è A1 àâòîìàòíûå ìíîæåñòâà ñëîâ.Òîãäà è ìíîæåñòâî A0 × A1 òàêæå àâòîìàòíî. Ïðè ýòîì àâòîìàò,ðàñïîçíàþùèé ÿçûê (A0 × A1 )♦ ñòðîèòñÿ ðàâíîìåðíî ïî àâòîìàòàì,ðàñïîçíàþùèì ÿçûêè A0 è A1 .Ïðåäëîæåíèå 3.2.2Äîêàçàòåëüñòâî. ßçûêèA0 {♦}∗èA1 {♦}∗ÿâëÿþòñÿ êîíêàòåíàöèÿìèàâòîìàòíûõ ÿçûêîâ è ïîýòîìó îíè òàêæå àâòîìàòíû.
Çàôèêñèðóåì àâ-Ai , i = 0, 1, ðàñïîçíàþùèå ýòè ìíîæåñòâà.♦ßçûê L(A0 × A1 ) ýòî óæå ïî÷òè (A0 × A1 ) : ëèøíèìè ÿâëÿþòk♦ñÿ òîëüêî îêîí÷àíèÿ ñëîâ âèäà, k ∈ N. Ýòè îêîí÷àíèÿ ìîæíî♦óáðàòü, âçÿâ ãîìîìîðôíûé îáðàç ÿçûêà L(A0 × A1 ) îòíîñèòåëüíî ãîìî♦ìîðôèçìà îòîáðàæàþùåãîâ Λ è òîæäåñòâåííîãî íà âñåõ îñòàëü♦òîìàòûíûõ ýëåìåíòàõ àëôàâèòà. Ïî òåîðåìå î ãîìîìîðôèçìå, ïîëó÷åííûé ÿçûê♦áóäåò àâòîìàòíûì. Îí æå áóäåò ñîâïàäàòü ñ (A0 × A1 ) . [Ïðåäëàãàåìîåèñïðàâëåíèå: Ìîæíî ñäåëàòü ññûëêó íà òåîðåìó 2.8.1 â ÿâíîìâèäå.]Ïðèìåð 3. Ñòðóêòóðà hN; +, 6i èìååò àâòîìàòíîå ïðåäñòàâëåíèå.. êà÷åñòâå àëôàâèòà âîçüì¼ì ìíîæåñòâî {0, 1}. Íàòóðàëüíûå ÷èñëàáóäóò ïðåäñòàâëÿòüñÿ ñâîèìè äâîè÷íûìè ðàçëîæåíèÿìè, çàïèñàííûìèíàîáîðîò, ðàññìàòðèâàåìûìè, êàê ñëîâà íàä ýòèì àëôàâèòîì, íàïðèìåð,4 áóäåò ïðåäñòàâëåíî äâîè÷íîé çàïèñüþ 001, 0 çàïèñüþ 0, 18 çàïèñüþ01001 è ò.ä.
Ìíîæåñòâî âñåõ âîçìîæíûõ äâîè÷íûõ çàïèñåé íàòóðàëüíûõ∗÷èñåë ðàâíî L = {0} ∪ {0, 1} {1}. Àâòîìàòíîñòü îòíîøåíèÿ ïîðÿäêà íàýòîì ìíîæåñòâå î÷åâèäíà.+♦ íà òàêèõ ðàçëîæåíèÿõ ÿâëÿåòñÿ[3]àâòîìàòíûì ïîäìíîæåñòâîì â {0, 1} , ìû ïðåäñòàâèì åãî â âèäå ïå3 ♦ðåñå÷åíèÿ àâòîìàòíîãî ìíîæåñòâà (L ) ñ íåêîòîðûì àâòîìàòíûì ìíî×òîáû ïîêàçàòü, ÷òî ìíîæåñòâîæåñòâîì. Îïèøåì àâòîìàò äëÿ äàííîãî ìíîæåñòâà.  ýòîì àâòîìàòå,ôàêòè÷åñêè èñïîëíÿþùåì ñëîæåíèå ÷èñåë "ñòîëáèêîì ïðè óñëîâèè, ÷òî÷èñëà çàïèñàíû â îáðàòíîì ïîðÿäêå, áóäåò äâà ñîñòîÿíèÿ, 0 è 1, ñîîòâåòñòâóþùèå ÷èñëó, êîòîðîå ìû äåðæèì "â óìå" â ïðîöåññå ñëîæåíèÿ:ìû èä¼ì ñïðàâà íàëåâî, ñêëàäûâàåì î÷åðåäíûå öèôðû, äîáàâëÿåì ê íèì÷èñëî, êîòîðîå ìû äåðæàëè "â óìå îïðåäåëÿåì î÷åðåäíóþ öèôðó îòâåòà, çàïîìèíàåì ñëåäóþùåå ÷èñëî, êîòîðîå ìû äåðæèì â óìå, è ò.ï.
Ïðè[3]èçîáðàæåíèè àâòîìàòà íàì áóäåò óäîáíî ñèìâîëû àëôàâèòà {0, 1}âèäà3.2. Ñâîéñòâà êîíâîëþöèé è çàìå÷àòåëüíûå ñâîéñòâà àâòîìàòíûõ ñòðóêòóð67x y z(x, y, z).èçîáðàæàòü â âèäåÍà ðèñóíêå èçîáðàæåí òðåáóåìûé àâ-òîìàò, â êîòîðîì ëþáîå âõîæäåíèå ñèìâîëàèç0è]îáîçíà÷àåò ëþáîé ñèìâîë♦:[Åñëè äâîè÷íûå ïðåäñòàâëåíèÿ íàòóðàëüíûõ ÷èñåë çàïèñàíûíàîáîðîò (òî åñòü 1 âñåãäà ÿâëÿåòñÿ ïîñëåäíèì ñèìâîëîì), òîïðè ñëîæåíèè äâóõ ÷èñåë ìû èäåì ñëåâà íàïðàâî, à íå ñïðàâà####íàëåâî.]####[Íà ðèñóíêå â ñàìîì âåðõó ñòðàíèöû ñòðåëêà, èäóùàÿ èç ñîñòîÿíèÿ 1 â íåãî æå, äîëæíà èìåòü òðåòüþ ïîìåòêó(1, ], 0),à íå(1, ], 1).]Ïðåäëîæåíèå 3.2.3 Åñëè A êîíå÷íûé àëôàâèò è ìíîæåñòâî L ⊆A∗ àâòîìàòíî, òî è âñå ìíîæåñòâà Ln , n > 0 àâòîìàòíû.
Ïðè ýòîìàâòîìàò, ðàñïîçíàþùèé ìíîæåñòâî (Ln )♦ ñòðîèòñÿ ðàâíîìåðíî ïî àâòîìàòó, ðàñïîçíàþùåìó L.Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ïðîâîäèòñÿ ïî òîé æå ñõåìå, ÷òî è âÏðåäëîæåíèè 3.2.2. Ïóñòü A = hQ, A, q, t, F i àâòîìàò, ðàñïîçíàþùèé∗ìíîæåñòâî L{♦} . n [n] [n] [n] n nÐàññìîòðèì àâòîìàò A = Q , A , q , t , F, â êîòîðîìq [n] = hq, . . . , qi ∈ Qn ,è äëÿ âñåõq1 , . .
. , qn ∈ Q, a1 , . . . , an ∈ A ∪ {♦} âûïîëíåíî a1t(q1 , a1 ) ..t[n] hq1 , . . . , qn i , ... = ..ant(qn , an )Êàê èóáåæäàåìñÿ,àâòîìàòAn ðàñïîçíà¼ò ÿçûê, ñîñòîÿùèé èç ÷òîðàíååa01a11ak−11 .. .. .. ñëîâ . . · · · , k ∈ N òàêèõ, ÷òî äëÿ âñåõ i 6 n âûïîë.01k−1anananÃëàâà 3. Àâòîìàòíûå ñòðóêòóðû68a0i , a1i . . . ak−1∈ L{♦}∗ .
Äàëåå, ÷òîáû óáðàòü íåíóæíûå îêîí÷àíèÿi♦ .. âèäà . , íóæíî âçÿòü îáðàç ýòîãî ÿçûêà îòíîñèòåëüíî ãîìîìîðôèç♦♦ . ìà, îòîáðàæàþùåãî .. â Λ è òîæäåñòâåííîãî íà âñåõ îñòàëüíûõ ýëå♦[n]n ♦ìåíòàõ àëôàâèòà A .  ðåçóëüòàòå ìû ïîëó÷èì àâòîìàòíûé ÿçûê (L ) ,÷òî è òðåáîâàëîñü. íåíîÏóñòü L àâòîìàòíûé ÿçûê è S ⊆ Ln àâòîìàòíîå ìíîæåñòâî. Òîãäà è ìíîæåñòâîÏðåäëîæåíèå 3.2.4T = {ᾱ♦ | ᾱ ∈ Ln \ S}òàêæå àâòîìàòíî. Ïðè ýòîì àâòîìàò, ðàñïîçíàþùèé T , ñòðîèòñÿðàâíîìåðíî ïî àâòîìàòàì, ðàñïîçíàþùèì S è L.Äîêàçàòåëüñòâî. Óòâåðæäåíèå ñëåäóåò èç òîãî, ÷òîT = (Ln )♦ \ S ♦ . Ïóñòü A íåêîòîðûé ÿçûê, è B ⊆ An àâòîìàòíîå ìíîæåñòâî, 1 6 k 6 n + 1. Òîãäà è ìíîæåñòâîÏðåäëîæåíèå 3.2.5T = {ha1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
