1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 12
Текст из файла (страница 12)
Çàìåòèì, ÷òî ìíîæåñòâàèLB = (PB )♦♦♦LA = (PA )♦♦∗∗àâòîìàòíû. Ïî Ïðåäëîæåíèþ 3.2.1, ìû ïîëó-÷èì, ÷òî ìíîæåñòâî, ñîñòîÿùåå èç ñëîâ âèäàãäå♦A0 A1 · · · Ak−1 ∈ LAèB0 B1 · · · Bk−1 ∈ LB ,A0B0A0B0àâòîìàòíî.···Ak−1Bk−1,[ÏÐÅÄËÀ-ÃÀÅÌÎÅ ÈÑÏÐÀÂËÅÍÈÅ: Ëó÷øå ñîñëàòüñÿ íà ïðåäëîæåíèå ♦ ♦ 3.2.2.] Ïðèìåíèâ ê ýòîìó ìíîæåñòâó ãîìîìîðôèçì, îòïðàâëÿþùèé ♦ ♦â Λ è âñå îñòàëüíûå ñèìâîëû â ñàìèõ ñåáÿ, ìû ñíîâà ïîëó÷èì àâòîìàòíîåìíîæåñòâî, êîòîðîå, êàê íåòðóäíî óáåäèòüñÿ, ïîëó÷àåòñÿ ñëåäóþùèì îáðàçîì: áåð¼ì âñåâîçìîæíûå ïàðûhγ0 , γ1 i ∈ A,óäîâëåòâîðÿþùèåPâA,Ãëàâà 3.
Àâòîìàòíûå ñòðóêòóðû74âñåâîçìîæíûå ïàðûhδ0 , δ1 i ∈ B,óäîâëåòâîðÿþùèåèõ äðóã íàä äðóãîì â ñëåäóþùåì ïîðÿäêå:PB,âðàñïîëàãàåìγ0 , γ1 , δ0 , δ1 , âûðîâíÿâ èõ ïî ëå-âîìó êðàþ; ïîñëå ýòîãî äîáàâëÿåì â êàæäóþ ïîëó÷åííóþ ñòðîêó íåìàêñèìàëüíîé äëèíû ñèìâîëû♦òàê, ÷òîáû âñå ñòðîêè ñòàëè îäèíàêîâîéäëèíû; ïîñëå ýòîãî îñòàëîñü êàæäûå ÷åòûðå ñèìâîëàa, b, c, d,ïîñëåäî-âàòåëüíî ðàñïîëîæåííûõ äðóã íàä äðóãîì, ïðåäñòàâèòü â âèäå ñèìâîëàa b . c dÌíîæåñòâî(PA×B )♦ïîëó÷àåòñÿ èç íåãî ïåðåñòàíîâêîé ñòðîêñèìâîëîâ (ïåðâàÿ è ÷åòâåðòàÿ îñòàþòñÿ íà ìåñòå, à âòîðàÿ è òðåòüÿ ìå-íÿþòñÿ ìåñòàìè) ñ ïîñëåäóþùåé çàìåíîé ôðàãìåíòîâ♦♦íà♦.Ýòèïðåîáðàçîâàíèÿ ìîæíî ïðåäñòàâèòü, êàê ïîñëåäîâàòåëüíîå ïðèìåíåíèå♦äâóõ ãîìîìîðôèçìîâ.
Ïî òåîðåìå î ãîìîìîðôèçìàõ, ÿçûê (PA×B ) òàêæå àâòîìàòåí.Ëþáàÿ êîíå÷íî ïîðîæä¼ííàÿ àáåëåâà ãðóïïà äîïóñêàåò àâòîìàòíîå ïðåäñòàâëåíèå.Ñëåäñòâèå 3.3.1Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, õîðîøî èçâåñòíî, ÷òî ëþáàÿ òàêàÿãðóïïà ðàçëàãàåòñÿ â äåêàðòîâî ïðîèçâåäåíèå êîíå÷íîãî ÷èñëà öèêëè÷åñêèõ ãðóïï. Êîíå÷íûå êîìïîíåíòû ýòîãî ðàçëîæåíèÿ àâòîìàòíî ïðåäñòàâèìû, à áåñêîíå÷íûå èçîìîðôíûhZ; +i, ïðåäñòàâèìîñòü äëÿ òàêèõ ãðóïïóæå äîêàçàíà íàìè. Äàëåå îñòàåòñÿ ïðèìåíèòü òåîðåìó.[ÏÐÅÄËÀÃÀ-ÅÌÎÅ ÈÑÏÐÀÂËÅÍÈÅ:  ïðåäïîñëåäíåé ñòðîêå äîêàçàòåëüñòâà òåîðåìû 3.3.1 ìîæíî ñîñëàòüñÿ íåïîñðåäñòâåííî íà òåî-Óïðàæíåíèå.hN; s, 6i.ðåìó 2.8.1.]ñòðóêòóðû3.4Ïîñòðîèòü àâòîìàòíîå ïðåäñòàâëåíèå äëÿÔàêòîðû àâòîìàòíûõ ñòðóêòóðmk−1 Ïóñòü A = A; P0m0 , .
. . , Pk−1 íåêîòîðàÿ àëãåáðàè÷åñêàÿ ñòðóêòóðà. Îòíîøåíèå ýêâèâàëåíòíîñòè E íà å¼ îñíîâíîì ìíîæåñòâå A íàçîâ¼ì îòíîøåíèåì êîíãðóýíòíîñòè (èëè ïðîñòîêîíãðóýíöèåé) íà A, åñëè îíî îáëàäàåò ñëåäóþùèì äîïîëíèòåëüíûìñâîéñòâîì:Îïðåäåëåíèå 3.4.13.4. Ôàêòîðû àâòîìàòíûõ ñòðóêòóð75äëÿ ëþáîãî i < k , èç Pi (x0 , . . . , xmi ) è hx0 , y0 i , . . . , hxmi , ymi i ∈E ñëåäóåò Pi (y0 , . . . , ymi ).E êîíãðóýíöèÿ íà A, òî ìîæíî îïðåäåëèòü òàê íàçûâàåìóþôàêòîðñèñòåìó A ïî E òîé æå ñàìîé ñèãíàòóðû, îáîçíà÷àåìóþ A/E ,ýëåìåíòàìè êîòîðîé áóäóò êëàññû ýêâèâàëåíòíîñòè E , è çíà÷åíèå ëþáîãîñèãíàòóðíîãî ñèìâîëà P îïðåäåëÿåòñÿ, êàêÅñëèA/E |= P (a1 /E, .
. . , am /E) ⇔ A |= P (a1 , . . . , am ),Ñâîéñòâà îòíîøåíèÿEäëÿ âñåõa1 , . . . , a m .îáåñïå÷èâàþò íàì êîððåêòíîñòü ýòîãî îïðåäåëå-íèÿ.E ïðîèçâîëüíàÿ ýêâèâàëåíòíîñòü íà A. Ìíîæåñòâî T íàçûâàåòñÿ òðàíñâåðñàëüþ îòíîøåíèÿ E , åñëè îíî ñîäåðæèò ðîâíî ïî îäíîìóýëåìåíòó èç êàæäîãî êëàññà ýêâèâàëåíòíîñòè E .ÏóñòüÄëÿ ëþáîãî àâòîìàòíîãî îòíîøåíèÿ ýêâèâàëåíòíîñòèíà àâòîìàòíîì ìíîæåñòâå ñóùåñòâóåò åãî àâòîìàòíàÿ òðàíñâåðñàëü.Òåîðåìà 3.4.1Äîêàçàòåëüñòâî. Ïóñòü E àâòîìàòíîå îòíîøåíèå ýêâèâàëåíòíîñòè íàS .
Òîãäà ïî äîêàçàííîìó ðàíåå ìíîæåñòâî {x ∈S | ∀y ∈ S(hx, yi ∈ E → x 6lex y)} òàêæå àâòîìàòíî è ïðè ýòîì ÿâëÿåòñÿòðàíñâåðñàëüþ äëÿ E . àâòîìàòíîì ìíîæåñòâåÏóñòü A àâòîìàòíàÿ ñòðóêòóðà, è E àâòîìàòíàÿ êîíãðóýíöèÿ íà íåé. Òîãäà è ó A/E ñóùåñòâóåò àâòîìàòíîåïðåäñòàâëåíèå.Ñëåäñòâèå 3.4.1Äîêàçàòåëüñòâî.  êà÷åñòâå îñíîâíîãî ìíîæåñòâà äàííîãî ïðåäñòàâëåíèÿ ìîæíî âçÿòü àâòîìàòíóþ òðàíñâåðñàëüTîòíîøåíèÿE,à âñå ïðå-äèêàòû íà í¼ì çàäàòü ñ ïîìîùüþ òåõ æå àâòîìàòîâ, êîòîðûå çàäàþòx ∈ T 7→ x/Eíà A/E . ïðåäèêàòû èñõîäíîé ìîäåëè. Ïðè ýòîì îòîáðàæåíèåÿâëÿòüñÿ èçîìîðôèçìîì èç ïîëó÷åííîé ñòðóêòóðûÇàìå÷àíèå.áóäåòÌîæíî áûëî áû îïðåäåëèòü àâòîìàòíûå ñòðóêòóðû òàê,÷òîáû êàæäîìó å¼ ýëåìåíòó ñîîòâåòñòâîâàëî, âîîáùå ãîâîðÿ, íåñêîëüêî ñëîâ ðåãóëÿðíîãî ÿçûêà, è îòíîøåíèå ¾x èyÿâëÿþòñÿ îáîçíà÷åíèÿ-ìè îäíîãî è òîãî æå ýëåìåíòà¿ áûëî áû àâòîìàòíûì.
Äàííîå ñëåäñòâèåïîêàçûâàåò, ÷òî íåò ñìûñëà äàâàòü òàêîå áîëåå ñëîæíîå îïðåäåëåíèå,ïîñêîëüêó âñ¼ ðàâíî òàêóþ ñòðóêòóðó ìîæíî ïðåäñòàâèòü òàê, ÷òîáûêàæäûé å¼ ýëåìåíò ñîîòâåòñòâîâàë â òî÷íîñòè îäíîìó ñëîâó.Ïðåäìåòíûé óêàçàòåëüA∗ , 8L(A), 16LT , 23Λ, 8µ(w), 23s(w), 23s · w, 16t∗ (s, w), 16ëåììààëôàâèò, 8ïîäñëîâî, 9àâòîìàòïðàâèëüíûé ñåãìåíò, 23î íàêà÷èâàíèè, 21íà÷àëüíûé ñåãìåíò, 9íàêà÷èâàíèå, 21îáúåäèíåíèå ÿçûêîâ, 10îòíîøåíèåêîíãðóýíòíîñòè, 74ïåðåñå÷åíèå ÿçûêîâ, 10äåòåðìèíèðîâàííûé, 15, 25ðàñïîçíàâàíèå ñëîâà àâòîìàòîì, 16ãðàôè÷åñêîå èçîáðàæåíèå, 17ðàâíîìåðíîñòü, 30íåäåòåðìèíèðîâàííûé ñî ñêà÷-ðàçíîñòü ÿçûêîâ, 10êàìè, 26ñåãìåíòàâòîìàòûýêâèâàëåíòíûå, 28ïðàâèëüíûé, 23ñëîâîäåðåâî, 23íàä àëôàâèòîì, 8äåòåðìèíèçàöèÿ àâòîìàòà, 31ïðèíèìàåìîå àâòîìàòîì, 16äëèíà ñëîâà, 8ïðèíèìàåìîå íåäåòåðìèíèðîâàí-äîïîëíåíèå ÿçûêà, 10íûì àâòîìàòîì, 27ýêâèâàëåíòíîñòü àâòîìàòîâ, 28ïðèíèìàåìîå íåäåòåðìèíèðîâàí-ôàêòîðàëãåáðà, 75íûì àâòîìàòîì ñî ñêà÷êàìè,ôàêòîðñèñòåìà, 7527ôàêòîðñòðóêòóðà, 75ïóñòîå, 8êîíå÷íûé àâòîìàò, 15ðàñïîçíàâàåìîå àâòîìàòîì, 16êîíå÷íûé ñåãìåíò, 9ðàñïîçíàâàåìîå íåäåòåðìèíèðî-êîíãðóýíöèÿ, 74âàííûì àâòîìàòîì, 27êîíêàòåíàöèÿðàñïîçíàâàåìîå íåäåòåðìèíèðî-ñëîâ, 9âàííûì àâòîìàòîì ñî ñêà÷-êîíêàòåíàöèÿ ÿçûêîâ, 10êàìè, 2776Ïðåäìåòíûé óêàçàòåëüñîäåðæàùåå ïîñëåäîâàòåëüíîñòü,23ñòåïåíü ñëîâà, 9ñâîéñòâîíàêà÷èâàíèÿ, 21òðàíñâåðñàëü, 75ÿçûêàâòîìàòà, 16àâòîìàòíûé, 16íàä àëôàâèòîì, 9ðàñïîçíàâàåìûé àâòîìàòîì, 16çâ¼çäî÷êà Êëèíè, 1077.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
