1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

. . , ak−1 , a, ak , . . . , an i | ha1 , . . . , an i ∈ B è a ∈ A}òàêæå àâòîìàòíî. Ïðè ýòîì àâòîìàò, ðàñïîçíàþùèé T ♦ , ñòðîèòñÿðàâíîìåðíî ïî àâòîìàòàì, ðàñïîçíàþùèì ìíîæåñòâà A è B ♦ .[ ôîðìóëèðîâêå ïðåäëîæåíèÿ 3.2.5 A äîëæíî îáîçíà÷àòüàâòîìàòíûé ÿçûê? Êàæåòñÿ, òóò A äîëæíî áûòü ïðîñòî àëôàâèòîì.

Àâòîìàòíîñòü A çàòåì èñïîëüçóåòñÿ â äîêàçàòåëüñòâå.Çàïÿòàÿ ïîñëå ñëîâà ÿçûê â ïåðâîé ñòðîêå ëèøíÿÿ]Äîêàçàòåëüñòâî. Äîêàæåì óòâåðæäåíèå äëÿ ñëó÷àÿk = n + 1.Äëÿîñòàëüíûõ ñëó÷àåâïðîâîäèòñÿ àíàëîãè÷íî. äîêàçàòåëüñòâî♦Ïóñòü n ðàç. Ïî Ïðåäëîæåíèþ 3.2.1, ÿçûê, ñîñòîÿùèé♦  x0x1xk−1ñëîâ···äëÿ êîòîðûõ ñïðàâåäëèâî x0 · · · xk−1 ∈y0y1yk−1♦n = èç...3.2.

Ñâîéñòâà êîíâîëþöèé è çàìå÷àòåëüíûå ñâîéñòâà àâòîìàòíûõ ñòðóêòóð69B ♦ {♦n }∗èy0 · · · yk−1 ∈ A {♦}∗ÿâëÿåòñÿ àâòîìàòíûì. Ïðèìåíèì ê ýòî-♦n♦ìó ÿçûêó ãîìîìîðôèçì, îòîáðàæàþùèéâ ïóñòîå ñëîâî, è òîæ-äåñòâåííûé íà âñåõ îñòàëüíûõ ñèìâîëàõ. Ïîëó÷èì ñíîâà àâòîìàòíûéÿçûê. Åñëè òåïåðüçàìåíèòüðàñïîçíàþùåìäàííûé ÿçûêâàâòîìàòå,âñå ñèìâîëû âèäàðàñïîçíàþùèéa0  ..    .   an−1bíàa0 .. . an−1bT ♦ , ÷òî è òðåáîâàëîñü. [Â,òî ìû ïîëó÷èì àâòîìàò,ñòðîêàõ 4-5 äîêàçàòåëüñòâàïðåäëîæåíèÿ 3.2.5 k íå òî æå ñàìîå, ÷òî â ñòðîêå 1.  ñòðîêå 4 äîêàçàòåëüñòâà ïåðåä äëÿ êîòîðûõ ñïðàâåäëèâî äîëæíàñòîÿòü çàïÿòàÿ]Ïóñòü L ïðîèçâîëüíûé ÿçûê, S ⊆ Ln+1 àâòîìàòíîå ìíîæåñòâî, è 1 6 k 6 n + 1.

Òîãäà è ìíîæåñòâîÏðåäëîæåíèå 3.2.6T = {ha1 , . . . , ak−1 , ak+1 , . . . , an+1 i | ∃y(ha1 , . . . , ak−1 , y, ak+1 , . . . , an+1 i ∈ S)}òàêæå àâòîìàòíî. Ïðè ýòîì àâòîìàò, ðàñïîçíàþùèé T , ñòðîèòñÿðàâíîìåðíî ïî àâòîìàòó, ðàñïîçíàþùåìó S .Äîêàçàòåëüñòâî. Íå îãðàíè÷èâàÿ îáùíîñòè äîêàçàòåëüñòâà, ìû ìîæåìñ÷èòàòü, ÷òîk = n + 1.Îïðåäåëèì ãîìîìîðôèçìθ : A[n+1] → A[n]çàäà-íèåì åãî çíà÷åíèé íà ñèìâîëàõ:♦ ..θ  . ♦x = Λ,Êàê ëåãêî âèäåòü,â îñòàëüíûõ ñëó÷àÿõθ(S) = T ,x1 ..θ  . x nxn+1  = x1...T,.xnîòêóäà ñëåäóåò àâòîìàòíîñòü ÿçûêàíîìåðíîñòü ïîñòðîåíèÿ àâòîìàòà, ðàñïîçíàþùåãîïðåäûäóùèõ ðåçóëüòàòîâ.T.Ðàâ-ëåãêî ñëåäóåò èçÃëàâà 3. Àâòîìàòíûå ñòðóêòóðû70Ïóñòü S0 , S1 àâòîìàòíûå ìíîæåñòâà nîê ñëîâíàä íåêîòîðûì àëôàâèòîì.

Òîãäà è ìíîæåñòâî S0 ∪ S1 òàêæå àâòîìàòíî. Ïðè ýòîì àâòîìàò, ðàñïîçíàþùèé ìíîæåñòâî (S0 ∪S1 )♦ , ñòðîèòñÿ ðàâíîìåðíî ïî àâòîìàòàì, ðàñïîçíàþùèì S0♦ è S1♦ .Ïðåäëîæåíèå 3.2.7(S0 ∪S1 )♦ = S0♦ ∪S1♦ . Îòñþäà ÿñíî, ÷òî â♦êà÷åñòâå àâòîìàòà, ðàñïîçíàþùåãî (S0 ∪ S1 ) , ìîæíî âçÿòü àâòîìàò, ðàñ♦♦ïîçíàþùèé îáúåäèíåíèå ÿçûêîâ S0 è S1 , êîòîðûé, êàê èçâåñòíî, ñòðîÄîêàçàòåëüñòâî. Çàìåòèì, ÷òîèòñÿ ðàâíîìåðíî ïî àâòîìàòàì, ðàñïîçíàþùèì ñîîòâåòñòâóþùèå ÿçûêè.Òåïåðü ìû â ñîñòîÿíèè äîêàçàòü âàæíûé ðåçóëüòàò î çàìå÷àòåëüíûõàëãîðèòìè÷åñêèõ ñâîéñòâàõ àâòîìàòíûõ ìîäåëåé.Ïóñòü A àâòîìàòíàÿ ñòðóêòóðà è ϕ(x̄) ôîðìóëàïåðâîãî ïîðÿäêà.

Òîãäà ìíîæåñòâî {ā | A |= ϕ(ā)} àâòîìàòíî, ïðè÷¼ì àâòîìàò, ðàñïîçíàþùèé ýòî ìíîæåñòâî ñòðîèòñÿ ðàâíîìåðíî ïîôîðìóëå ϕ è íàáîðó ïåðåìåííûõ x̄.Òåîðåìà 3.2.1Äîêàçàòåëüñòâî. Áåç îãðàíè÷åíèÿ îáùíîñòè ìû ìîæåì ñ÷èòàòü, ÷òîôîðìóëàϕñîäåðæèò òîëüêî ñâÿçêè∨, ¬è òîëüêî ýêçèñòåíöèàëüíûåêâàíòîðû. Äàëåå ïðåäëîæåíèå äîêàçûâàåòñÿ ïî èíäóêöèè.

Áàçà èíäóêöèè î÷åâèäíà. Äàëåå äîêàçàòåëüñòâî ïðîäîëæàåòñÿ ñ èñïîëüçîâàíèåì ïðåäëîæåíèé 3.2.43.2.7.[ÑÞÄÀ: Îïðåäåëåíèå ýëåìåíòàðíîé òåîðèè, êîíñòðóêòèâèçàöèè è ñèëüíîé êîíñòðóêòèâèçàöèè.]Ðàçðåøèìîñòü ýëåìåíòàðíîé òåîðèè è, òåì áîëåå, íàëè÷èå ñèëüíîéêîíñòðóêòèâèçàöèè âñòðå÷àþòñÿ íå ñëèøêîì ÷àñòî è ÿâëÿþòñÿ î÷åíüöåííûìè àëãîðèòìè÷åñêèìè õàðàêòåðèñòèêàìè ñòðóêòóðû. Áîëåå òîãî,àâòîìàòíîñòü âñåõ ôîðìóëüíûõ ìíîæåñòâ ïîçâîëÿåò óñòàíàâëèâàòü ïðèíàäëåæíîñòü ê íèì ñ î÷åíü íåáîëüøèìè çàòðàòàìè: âñåãî ëèøü çà âðåìÿ,îãðàíè÷åííîå ëèíåéíîé ôóíêöèåé îò äëèíû âõîäíûõ äàííûõ (ñëîâ â àëôàâèòå).Ñëåäñòâèå 3.2.1 Åñëè A àâòîìàòíàÿ ñòðóêòóðà, òî å¼ ýëåìåíòàðíàÿ òåîðèÿ ðàçðåøèìà, è ýòà ñòðóêòóðà îáëàäàåò ñèëüíîé êîíñòðóêòèâèçàöèåé.3.2.

Ñâîéñòâà êîíâîëþöèé è çàìå÷àòåëüíûå ñâîéñòâà àâòîìàòíûõ ñòðóêòóð71Äîêàçàòåëüñòâî.  êà÷åñòâå ñèëüíîé êîíñòðóêòèâèçàöèè ñòðóêòóðûAìîæíî âçÿòü íóìåðàöèþ, ïîëó÷åííóþ èç ã¼äåëåâîé íóìåðàöèè ìíîæåñòâà âñåõ ñëîâ íàä àëôàâèòîì. ×òîáû îòâåòèòü íà âîïðîñ îá èñòèííîñòèôîðìóëû íà êîðòåæå èç çíà÷åíèé, íàäî ýôôåêòèâíî íàéòè ñîîòâåòñòâóþùèé àâòîìàò, ñîñòàâèòü êîíâîëþöèþ êîðòåæà è ñ ïîìîùüþ ïîëó÷åííîãîàâòîìàòà ïðîâåðèòü èñòèííîñòü.

Ðàçðåøèìîñòü òåîðèè ïîëó÷àåì íåïîñðåäñòâåííî èç ñóùåñòâîâàíèÿ ñèëüíîé êîíñòðóêòèâèçàöèè.Èç äîêàçàííîãî ñëåäñòâèÿ ìû ïîëó÷àåì, ÷òî âñå óæå ïåðå÷èñëåííûåêîíêðåòíûå àâòîìàòíûå ñòðóêòóðû, à òàêæå òå àâòîìàòíûå ñòðóêòóðû,êîòîðûå áóäóò ïåðå÷èñëåíû äàëåå, îáëàäàþò î÷åíü ñèëüíûìè àëãîðèòìè÷åñêèìè ñâîéñòâàìè, â ÷àñòíîñòè, îíè èìåþò ñèëüíûå êîíñòðóêòèâèçàöèè è ðàçðåøèìûå òåîðèè.Ïðèìåð 4. Ñòðóêòóðà hZ; +, 6i (ìíîæåñòâî öåëûõ ÷èñåë ñ îïåðàöèåéñëîæåíèÿ è îáû÷íûì ïîðÿäêîì) ÿâëÿåòñÿ àâòîìàòíîé. êà÷åñòâå àëôàâèòà âîçüì¼ì ìíîæåñòâî {−, 0, 1}.

Öåëûå ÷èñëà áóäóòïðåäñòàâëÿòüñÿ êàê è â óæå ðàññìîòðåííîì ïðèìåðå âûøå ïðèìåðå äëÿíàòóðàëüíûõ ÷èñåë â âèäå äâîè÷íûõ ðàçëîæåíèé,çàïèñàííûõ íàîáîðîò,âîçìîæíî ñ çíàêîì ìèíóñ ïåðåä íèìè (äëÿ îòðèöàòåëüíûõ ÷èñåë). Íàïðèìåð, ÷èñëî 6 áóäåò ïðåäñòàâëåíî ñëîâîì011, ÷èñëî 10 ñëîâîì 0101,à ÷èñëî -10 ñëîâîì -0101.ÌíîæåñòâîAâñåõ ïðåäñòàâëåíèé ñîñòîèò èç òð¼õ íåïåðåñåêàþùèõ∗ñÿ àâòîìàòíûõ ìíîæåñòâ: {0} äëÿ 0, A+ = {0, 1} {1} äëÿ ïîëî∗æèòåëüíûõ ÷èñåë è A− = {−}{0, 1} {1} äëÿ îòðèöàòåëüíûõ ÷èñåë,A = A− ∪ {0} ∪ A+ .×èòàòåëþ ïðåäëàãàåòñÿ â êà÷åñòâå óïðàæíåíèÿ äîêàçàòü àâòîìàòíîñòü îòíîøåíèÿ ïîðÿäêà íà òàêèõ ñëîâàõ, ñîîòâåòñòâóþùåãî ïîðÿäêóíà íàòóðàëüíûõ ÷èñëàõ.hN; +i äëÿZ.Ìû îñòàâëÿåì ÷èòàòåëþ äîêàçàòåëüñòâî àâòîìàòíîñòè îòíîøåíèé x >0 è x = |y| (çäåñü |y| áóäåò îáîçíà÷àòü àáñîëþòíóþ âåëè÷èíó ÷èñëà y ).Êàê óæå áûëî îòìå÷åíî, îòíîøåíèå x + y = z íà A+ àâòîìàòíî.Òåïåðü îñòàëîñü îïðåäåëèòü ñëîæåíèå íà A ôîðìóëîé ïåðâîãî ïîÄàëåå ìû èñïîëüçóåì ðàíåå ïîëó÷åííîå ïðåäñòàâëåíèå äëÿäîêàçàòåëüñòâà àâòîìàòíîñòè ãðàôèêà ôóíêöèè ñëîæåíèÿ íàðÿäêà ñ èñïîëüçîâàíèåì óïîìÿíóòûõ îòíîøåíèé.

Ýòî ìîæíî ñäåëàòü ñïîìîùüþ ñëåäóþùåé ýêâèâàëåíòíîñòè:[Ñì. ïðåäëàãàåìîå èñïðàâëå-Ãëàâà 3. Àâòîìàòíûå ñòðóêòóðû72íèå ïðî ñòð 71.]x + y = z ⇔ (x, y > 0 ∧ x + y = z) ∨(x, y, z 6 0 ∧∃x0 y 0 z 0 (x0 = |x| ∧ y 0 = |y| ∧ z 0 = |z| ∧ x0 + y 0 = z 0 )) ∨(x > 0 ∧ y, z 6 0 ∧ ∃y 0 z 0 (y 0 = |y| ∧ z 0 = |z| ∧ x + y 0 = z 0 )) ∨(x, y > 0 ∧ z 6 0 ∧ ∃y 0 z 0 (y 0 = |y| ∧ z 0 = |z| ∧ x0 + z 0 = y 0 )) ∨(x, z > 0 ∧ y 6 0 ∧ ∃y 0 (y 0 = |y| ∧ y 0 + z = x) ∨(x, z 6 0 ∧ y 6 0) ∧ ∃x0 z 0 (x = y 0 + z 0 )). ïðàâîé ÷àñòè ýòîé ýêâèâàëåíòíîñòè èñïîëüçóþòñÿ îòíîøåíèÿy=z3.3òîëüêî ìåæäó ýëåìåíòàìè èçx+A+ .Äåêàðòîâû ïðîèçâåäåíèÿ àâòîìàòíûõ ñòðóêòóðmkm1Íàïîìíèì, ÷òî äåêàðòîâûì ïðîèçâåäåíèåì ñòðóêòóð A = hA; P1 , .

. . , Pk imm1kè B = hB; Q1 , . . . , Qk i îäèíàêîâîé ñèãíàòóðû íàçûâàåòñÿ ñòðóêòóðàA × B = hA × B; R1m1 , . . . , Rkmk i ,i = 1, . . . , k , a1 , . . . , ami ∈ A, b1 , . . . , bmi ∈ B óòâåðæäåíèå Ri (ha1 , b1 i , . . . , hami , bmi i) âûïîëíåíî òîãäà è òîëüêî òîãäà, êîãäàPi (a1 , . . . , ami ) è Qi (b1 , .

. . , bmi ).â êîòîðîé äëÿ ëþáûõÄåêàðòîâî ïðîèçâåäåíèå àâòîìàòíûõ ñòðóêòóð òîæåäîïóñêàåò àâòîìàòíîå ïðåäñòàâëåíèå.Òåîðåìà 3.3.1Äîêàçàòåëüñòâî. ÏóñòüAèB äâå àâòîìàòíûå ñòðóêòóðû îäíîé èòîé æå êîíå÷íîé ïðåäèêàòíîé ñèãíàòóðû ñ îñíîâíûìè ìíîæåñòâàìèBAèñîîòâåòñòâåííî, ñîñòîÿùèìè èç ñëîâ íàä íåêîòîðûìè àëôàâèòàìè. Îñ-íîâíûì ìíîæåñòâîì äëÿ àâòîìàòíîãî ïðåäñòàâëåíèÿ ñòðóêòóðû A0 × B♦áóäåò ìíîæåñòâî (A × B) , åñòåñòâåííûì îáðàçîì îòîæäåñòâëÿåìîå ñîìíîæåñòâîì ïàð èçA × B.[Ïðåäëàãàåìîå èñïðàâëåíèå: Ïîñëå òî÷-êè ìîæíî íàïèñàòü: Ñîãëàñíî ïðåäëîæåíèþ 3.2.2, ìíîæåñòâîAxB àâòîìàòíî.] Äëÿ äîêàçàòåëüñòâà óòâåðæäåíèÿ íàì íåîáõîäèìî3.3.

Äåêàðòîâû ïðîèçâåäåíèÿ àâòîìàòíûõ ñòðóêòóðäëÿ ëþáîãî ïðåäèêàòíîãî ñèãíàòóðíîãî ñèìâîëàP73ñèãíàòóðû äîêàçàòüàâòîìàòíîñòü ìíîæåñòâà êîíâîëþöèé(S1 , . . . , Sk )♦ | S1 , . . . , Sk ∈ (A × B)♦ ∧ A × B |= P (S1 , . . . , Sk ) .P.M áóäåì îáîçíà÷àòü PM . Äëÿ ïðå-Ìû äîêàæåì çäåñü íàøå óòâåðæäåíèå äëÿ áèíàðíûõ ïðåäèêàòîâÈíòåðïðåòàöèþ ïðåäèêàòàPâ ìîäåëèäèêàòîâ ñ äðóãèìè êîëè÷åñòâàìè àðãóìåíòîâ äîêàçàòåëüñòâî ïðîâîäèòñÿàíàëîãè÷íûì îáðàçîì.Èòàê, íàäî äîêàçàòü, ÷òî ìíîæåñòâî(PA×B )♦ àâòîìàòíî. Ïðåæäå, ÷åìïðîäîëæàòü äîêàçàòåëüñòâî, ñòîèò âçãëÿíóòü íà òî, êàê âûãëÿäÿò ýëåìåíòû ýòîãî ìíîæåñòâà. Ïðåäïîëîæèì, ÷òîè ñëîâàα0 , α1 , β0 , β1A |= P (α0 , α1 ), B |= P (β0 , β1 ),èìåþò ñëåäóþùèå çàïèñè ÷åðåç ñèìâîëû:α0 = a00 a10 , α1 = a01 a11 a21 , β0 = b00 , β1 = b01 b11 b21 b31 .((α0 , β0 )♦ , (α1 , β1 )♦ )♦ , ñâèäåòåëüñòâóþùåå î òîì, ÷òî A ×B |= P (hα0 , β0 i , hα1 , β1 i) âî ìíîæåñòâå (PA×B )♦ , èìååò ñëåäóþùèé âèä: 0  1 a0a0 b00   ♦   ♦   ♦       a0   a1   a21   ♦  .11b21b31b11b01Òîãäà ñëîâîÌû äîêàæåì, ÷òî ìíîæåñòâî ÿâëÿåòñÿ ãîìîìîðôíûì îáðàçîì íåêîòîðîãî àâòîìàòíîãî ìíîæåñòâà.

Характеристики

Список файлов лекций