Iv_task5 (Задание 5)

Ñåðãåé Èâàíû÷åâÃðóïïà 376ÔÓÏÌ ÌÔÒÈsergeyivanychev@gmail.comvk.com/ivanychevsergey+79104577995Âåðñèÿ 1.1Çàäàíèå 5Ðåãóëÿðíûå ÿçûêè: èòîãîâîå çàäàíèå.Çàäà÷à 1Îïðåäåëåíèå, íà îñíîâàíèè êîòîðîãî âåäåòñÿ äàëüíåéøåå ðàññóæäåíèå çâó÷èò ñëåäóþùèìîáðàçîì âçÿòî èç Âèêèïåäèè. Ñîãëàñíî ýòîìó îïðåäåëåíèþ,ïðàâèëüíûå ñêîáî÷íûå ïîñëåäîâàòåëüíîñòè îáðàçóþò ÿçûê Äèêà è ôîðìàëüíî îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì:ïóñòàÿ ñòðîêà ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü;• ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü, âçÿòàÿ â ñêîáêè îäíîãî òèïà ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü;• ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü, ê êîòîðîé ïðèïèñàíà ñëåâà èëè ñïðàâàïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü òîæå ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü.•Îäíèì èç ñâîéñòâ ÿçûêà Äèêà D2 ÿçûêà ïðàâèëüíûõ ñêîáî÷íûõ âûðàæåíèé ñ äâóìÿ òèïàìè ñêîáîê ÿâëÿåòñÿ ðàâåíñòâî êîëè÷åñòâ îòêðûâàþùèõ è çàêðûâàþùèõ ñêîáîê îäíîãîòèïà.

Òàê ∀w ∈ D2 , |w|( = |w|) .Ïóñòü ýòî íå òàê, òî åñòü ñóùåñòâóåò ÑÏ ñ íåðàâíûì êîëè÷åñòâîì îòêðûâàþùèõñÿ è çàêðûâàþùèõñÿ ñêîáîê îäíîãî òèïà, òîãäà äàííàÿ ÑÏ (áåç ïîòåðè îáùíàñòè ðàññìàòðèâàåìíåðàâíûå ïî êîëè÷åñòâó ñêîáêè (, ), îáîçíà÷èì åå b) íå ÿâëÿåòñÿ ïóñòîé ñòðîêîé, òî åñòüïî îïðåäåëåíèþ b = (b0 ), b = [b00 ] èëè b = b1 b2 , ãäå |b| > |b0 |, |b00 ||b1 |, |b2 |. Åñëè â b - íåðàâíîå êîëè÷åñòâî ñêîáîê (, ), òîãäà â b0 , b00 òàêæå íåðàâíîå êîëè÷åñòâî ïîäîáíûõ ñêîáîê èëè,â ñëó÷àå 3, â êàêîé-òî èç ïîäïîñëåäîâàòåëüíîñòåé b1 , b2 íåðàâíîå êîëè÷åñòâî ïîäîáíûõñêîáîê. Òîãäà ðàññìîòðèì ñîîòâåòñòâåííóþ, ìåíüøóþ ïî äëèíå ïîäñòðîêó è ïðèìåíèì äëÿíåå ýòè æå ðàññóæäåíèÿ.Òàê êàê äëèíà èçíà÷àëüíîé ñòðîêè áûëà êîíå÷íîé, òî â ñî÷åòàíèè ñ òåì, ÷òî êàæäàÿ ïîäîáíàÿ ïîäñòðîêà íå ÿâëÿåòñÿ ïóñòîé ñòðîêîé, ìû ïðèõîäèì ê ïðîòèâîðå÷èþ, òàê êàê â èòîãåïîëó÷àåì ïðè êîíå÷íîé ïîëñëåäîâàòåëüíîñòè äàííûõ ðàññóæäåíèé ïîäñòðîêó äëèíîé ìåíüøåé èëè ðàâíîé íóëÿ, ÷åãî áûòü íå ìîæåò, èç ÷åãî ñëåäóåò äîêàçûâàåìîå óòâåðæäåíèå1Ïóñòü äàííûé ÿçûê ÿâëÿåòñÿ ðåãóëÿðíûì, òîãäà äëÿ íåãî ñïðàâåäëèâà ëåììà î íàêà÷êå.Ïóñòü p êîíñòàíòà èç ëåììû, òîãäà ðàññìîòðèì ñëîâî w = (p )p [].

Äàííîå ñëîâî ÿâëÿåòñÿïðàâèëüíîé ñêîáî÷íîé ïîñëåäîâàòåëüíîñòüþ ñîãëàñíî îïðåäåëåíèþ, òàê êàêw = w1 w2 , w1 = (p )p , w2 = [ ]Ãäå w êîíêàòåíàöèÿ ñêîáî÷íûõ ïîñëåäîâàòåëüíîñòåé w1 è w2 , êàæäàÿ èç êîòîðûõ ÿâëÿåòñÿïðàâèëüíîé, òàê êàê âòîðàÿ âçÿòàÿ â ñêîáêè ïóñòàÿ ñòðîêà (ðåêóðåíòíûå ïðàâèëà 1 è 2),ïåðâàÿ n ðàç âçÿòàÿ â ñêîáêè ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü, òàê êàê íàïîñëå ïåðâîãî øàãà w11 = () ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü, íà i-ì øàãå ïðèw1i−1 ÏÑÊ, ñëåäóåò, ÷òî w1i = (w1i−1 ) ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü ïîðåêóðåíòíîìó ïðàâèëó 2.

Ïî èíäóêöèè ïîëó÷àåì, ÷òî w1 ≡ w1p ÏÑÊ, òî åñòü w = w1 w2 êîíêàòåíàöèÿ äâóõ ÏÑÊ, ò.å. ÏÑÊ.Äëÿ ñëîâà w ïî òåîðåìå î íàêà÷êå, ∃w = xyz : |y| > 0, íî òîãäà y = (k , k 6= 0 ⇒ w0 :w0 = xyyz, |w0 |( 6= |w0 |) , òàê êàê |w|( = |w|) , òî åñòü w0 íå ïðèíàäëåæèò ÿçûêó Äèêà, òî åñòüëåììà î íàêà÷êå íå ðàáîòàåò äëÿ ýòîãî ÿçûêà, òîãäà îí íå ÿâëÿåòñÿ ðåãóëÿðíûì.Çàäà÷à 2Ñ÷èòàåì, ÷òî â ëþáîì òðîè÷íîì ïðåäñòàâëåíèè ñëîâà èç L ñóùåñòâóåò òðåòèé ñèìâîë ñêîíöà, íå ÿâëÿþùèéñÿ ëèäèðóþùèì íóëåì.  òðîè÷íîé çàïèñè òðåòèé ñèìâîë ñïðàâà 2, òîåñòü äîïóñòèìû 32 = 9 ðàçëè÷íûõ âàðèàíòîâ òðåõ ïîñëåäíèõ ñèìâîëîâ (íà ïðåäïîñëåäíåéè ïîñëåäíåé ïîçèöèÿõ ìîãóò áûòü 0, 1, 2) {200, 201, 202, 210, 211, 212, 220, 221, 222}.Ïóñòü w - íåêîòîðîå íàòóðàëüíîå ÷èñëî, w = an .

. . a0 ïðåäñòàâëåíèå ÷èñëà â òðîè÷íîìâèäå, ãäå an ïåðâàÿ íåíóëåâàÿ öèôðà ñëåâà.w=nXai 3i(1)i=0ÏóñòüS ∗ = {n| n = 2 · 32 + a1 31 + a0 30 , a2 , a1 , a0 ∈ {0, 1, 2}}(2)Ãäå S ìíîæåñòâî îñòàòêîâ ïðè äåëåíèè íà 33 = 27. Ñ÷èòàÿ ïîíÿòèÿ L è ìíîæåñòâî ÷èñåë,ïîëó÷àþùèõñÿ èíòåðïðåòàöèåé ñëîâ èç L êàê äâîè÷íûå ïðåäñòàâëåíèÿ, ýêâèâàëåíòíûìè èîáîçíà÷àÿ çà L, äîêàæåì ÷òî L = {n| n mod 27 ∈ S ∗ } ≡ QQ ⊂ L, òàê ∀q ∈ Q â òðîè÷íîì ïðåäñòàâëåíèè èìåþò äâîéêó â êà÷åñòâå âòîðîãî ñïðàâàñèìâîëà. Ýòî ñëåäóåò èç òîãî, ÷òî, òàê êàê ëþáîå íàòóðàëüíîå ÷èñëî îäíîçíà÷íî ïðåäñòàâëÿåòñÿ â âèäå 1, òî îñòàòîê îò äåëåíèÿ íà 33 áóäóò õàðàêòåðèçîâàòü ëèøü êîýôôèöèåíòûïðè 32 , 31 , 30 , òàê êàê âñå îñòàëüíûå íàòóðàëüíûå ñòåïåíè òðîéêè äåëÿòñÿ íà 27.

Êîýôôèöèåíòû ïðè ýòèõ òðåõ ñòåïåíÿõ áóäóò õàðàêòåðèçîâàòü ïîñëåäíèå òðè öèôðû â òðîè÷íîì2ïðåäñòàâëåíèè, ïðè ýòîì êîýôôèöèåíò ïðè 32 ðàâåí 2, ÷òî ñëåäóåò èç ïðèíàäëåæíîñòèîñòàòêà îò äåëåíèÿ q íà 27 ê ìíîæåñòâó S∗ è îäíîçíà÷íîñòè ïðåäñòàâëåíèÿ â âèäå 1.L ⊂ Q, òàê êàê ∀l ∈ L, îñòàòîê îò äåëåíèÿ l íà 27 áóäåò ëåæàòü â ìíîæåñòâå S ∗ , òàê êàêòðåòüÿ ñ êîíöà öèôðà l ðàâíà 2, à â ìíîæåñòâå S ∗ ïðèñóòñòâóþò âñå âîçìîæíûå îñòàòêèïðè äåëåíèè íà 27 ïðè òðåòüåé ñ êîíöà äâîéêå, ÷òî ñëåäóåò èç îïðåäåëåíèÿ ìíîæåñòâà.Èòàê L = Q, òî åñòü ÄÊÀ äîëæåí ðàñïîçíàâàòü ÷èñëà ñ îñòàòêàìè, ëåæàùèìè â S ∗ èòîëüêî èõ.Çàäàäèì àâòîìàò ñëåäóþùèì îáðàçîì:A = (Q, Σ, qin , δ, F )Q = {qin , q0 , .

. . , q26 }Σ = (0, 1)δ : (qi , 0) → qj : j = 2i mod 27; (qi , 1) → qk : k = (2i + 1) mod 27, i ∈ [0 . . . 26];(qin , 0) → q0 , (qin , 1) → q1F = {qi |i ∈ S ∗ }(3)Îáðàòèì âíèìàíèå íà òî, ÷òî äàííûé àâòîìàò äåòåðìåíèðîâàííûé, òàê êàê ïî ëþáîéïàðå (w, l ∈ Σ) îòîáðàæåíèå îïðåäåëåíî â åäèíñòâåííóþ âåðøèíó.Ïóñòü w âõîäíîå ñëîâî. Äîêàæåì, ÷òî, ëèáî w = ε, ëèáî èíäåêñ j ñîñòîÿíèÿ (qin , w) `∗(qj , ε) ðàâåí îñòàòêó îò äåëåíèÿ ÷èñëà n, ÿâëÿþùåãîñÿ äâîè÷íîé èíòåðïðåòàöèåé ñëîâà w,íà 27.1.Áàçà èíäóêöèè.

Èç âåðøèíû qin èìååì ïåðåõîä â q0, q1 ïðè ïåðåõîäå ïî 0, 1 ñîîòâåò-2.Øàã èíäóêöèè Ïóñòü w0 6= 0 ñ÷èòàíî è w0 mod 27 = i, ïðè ýòîì àâòîìàò íàõîäèòñÿ âñòâåííî, èíäåêñû êîòîðûõ ðàâíû ñîîòâåòñòâåííûì îñòàòêàì ïðè äåëåíèè íà 27ñîñòîÿíèè qi , òîãäà• qi 6= qin , òàê êàê â qin íåò ïåðåõîäîâ.• Ïðè ñ÷èòûâàíèè íóëÿ èìååì ñ÷èòàííîå ñëîâî w0 0, çíà÷åíèå êîòîðîãî 2 · w0 , òîåñòü èç ñâîéñòâ àðèôìåòèêè îñòàòêîâ 2 · w0 mod 27 = 2i mod 27. Ïðè ýòîì èçîïðåäåëåíèÿ δ íîâûé èíäåêñ ñîñòîÿíèÿ òàêæå ðàâåí 2i mod 27 (ïðè ïåðåõîäåïî 0), òî åñòü èíäåêñ ñîñòîÿíèÿ ïðè ñ÷èòàííîì ïîäñëîâå w0 0 ñîâïàäàåò ñ åãîîñòàòêîì ïðè äåëåíèè íà 27• Ïðè ñ÷èòûâàíèè åäèíèöû èìååì ñ÷èòàííîå ñëîâî w0 1, çíà÷åíèå êîòîðîãî 2·w0 +1,òî åñòü àíàëîãè÷íî ïóíêòó âûøå èìååì èíäåêñ ñîñòîÿíèÿ ïðè ñ÷èòàííîì ïîäñëîâå w0 1 ñîâïàäàåò ñ åãî îñòàòêîì ïðè äåëåíèè íà 27.3.

Èç êîíå÷íîñòè w èìååì ëèáî òî, ÷òî w = ε, ëèáî (qin , w) `∗ (qj , ε) : j = w mod 27 èçèíäóêöèè. Óòâåðæäåíèå äîêàçàíî.Òåïåðü äîêàæåì, ÷òî L = L(A).3L ⊂ L(A), òàê êàê ∀l ∈ L, l mod 27 ∈ S ∗ , è, â ÷àñòíîñòè, l 6= ε. Èç äîêàçàííîãî âûøåóòâåðæäåíèÿ ñëåäóåò, ÷òî èíäåêñ êîíå÷íîãî äëÿ l ñîñòîÿíèÿ ëåæèò â S ∗ , òî åñòü êîíå÷íîåäëÿ l ñîñòîÿíèå ÿâëÿåòñÿ ïðèíèìàþùèì ïî îïðåäåëåíèþ ìíîæåñòâà F àâòîìàòà A.L(A) ⊂ L.

∀w ∈ L(A), w mod 27 ∈ S ∗ èç îïðåäåëåíèÿ àâòîìàòà, íî òîãäà w ∈ Q ≡ L.L = L(A), òî åñòü èñêîìûé ÄÊÀ ïîñòðîåí.Çàäà÷à 3Çàäà÷à 4Ïîñòðîèì A è B , êîòîðûå ðàñïîçíàþò ñîîòâåòñòâåííî ÿçûêè, â êîòîðîì íåò òðåõ áóêâ aïîäðÿä(L1 ) è â êîòîðîì ÷èñëî áóêâ b â êàæäîì ñëîâå ÷åòíî(L2 ).A:bq0baaq1q2aq3a, bbÄîêàæåì, ÷òî àâòîìàò A ðàñïîçíàåò ÿçûê L1 .Ïóñòîå ñëîâî ïðèíèìàåòñÿ àâòîìàòîì è ëåæèò â L1 . ∀w ∈ L1 , w ∈ L(A). Ïóñòü ýòî íå òàê,òîãäà êîíå÷íûì ñîñòîÿíèåì ïðè ðàñïîçíàâàíèè íåêîãî w ∈ L1 , ñòàëî q3 , íî â q3 ìîæíîqaaïîïàñòü òîëüêî ïî îòîáðàæåíèþ q2 −→ q3 , â q2 òîëüêî ïî q1 −→ q2 , â q1 òîëüêî ïî q0 →− 1 , òîåñòü â ñëîâå w åñòü ïîäñëîâî aaa, ÷òî ïðîòèâîðå÷èò ïðèíàäëåæíîñòè L1 .Äîêàæåì, ÷òî L(A) ⊂ L1 .

Îêîí÷àíèå â q0 , q1 èëè q2 îçíà÷àåò, ÷òî â ñëîâå, ïðîàíàëèçèðîâàííîì àâòîìàòîì, íå áûëî ïîäñëîâà aaa, òàê êàê â ïðîòèâíîì ñëó÷àå ïðè íà÷àëå ñ÷èòûâàíèÿäàííîãî ïîäñëîâà, èç ëþáîãî ñîñòîÿíèÿ ìû ïîïàäàåì â q3 :q0q1q2q3→ q1→ q2→ q3→ q3→ q2→ q3→ q3→ q3Ñëåäîâàòåëüíî, L(A) = L1 .B:4→ q3→ q3→ q3→ q3(4)bq0q1baaL2 ∈ L(B) Òàê êàê àâòîìàò ìåíÿåò ñîñòîÿíèå ñ q0 íà q1 è íàîáîðîò òîëüêî ïðî÷èòàâ î÷åaa→ q1 .→ q0 , q1 −ðåäíóþ áóêâó b. Ïðè ñ÷èòûâàíèè a àâòîìàò íå ìåíÿåò ñîñòîÿíèÿ, òàê êàê q0 −∀w ∈ L2 , |w|b mod 2 = 0, òî åñòü àâòîìàò ïîìåíÿåò ñîñòîÿíèå ÷åòíîå ÷èñëî ðàç, òî åñòüêîíå÷íûì ñîñòîÿíèåì áóäåò q0 , ÿâëÿþùååñÿ ïðèíèìàþùèì.L(B) ∈ L2 , òàê êàê ïðèíÿòîå ñëîâî ìåíÿëî ñîñòîÿíèå ÷åòíîå ÷èñëî ðàç, ïðè ýòî ñîñòîÿíèåìåíÿåòñÿ íà äðóãîå ëèøü ïðè ïåðåõîäå ïî b, òî åñòü ∀w ∈ L(B), |w|b mod 2 = 0.Òàêèì îáðàçîì L2 = L(B).Îòìåòèì, ÷òî îáà ïîñòðîåííûõ àâòîìàòà ÿâëÿåòñÿ ïîëíûìè, òîãäà ïîñòðîèì L = L1 ∪ L2ðàâíûé ïåðåñå÷åíèþ ýòèõ ÿçûêîâ, òàê êàê äëÿ ñëîâ èç L è òîëüêî íèõ âûïîëíÿþòñÿ îáàñâîéñòâà.

Ïîñòðîèì àâòîìàò ïî àëãîðèòìó ïîñòðîåíèÿ ÄÊÀ ïåðåñå÷åíèÿ ÿçûêîâ. Ñ÷èòàåì,÷òî ïåðâûé ýëåìåíò â ïàðå ñîñòîÿíèå èç B , à âòîðîå èç A.(0, 1)a(0, 2)aaa(0, 0)(0, 3)bbb bb b(1, 3)(1, 0)bbaa(1, 2)aa(1, 1)Äàííûé àâòîìàò ÿâëÿåòñÿ ïîëíûì, òîãäà ïî óòâåðæäåíèþ, äîêàçàííîìó â ïðåäûäóùåì5çàäàíèè â ïðåäïîñëåäíåé çàäà÷å, ñëåäóåò, ÷òî ïðè èíâåðòèðîâàíèè ïðèíèìàåìîñòè êàæäîéâåðøèíû ìû ïîëó÷èì àâòîìàò, ðàñïîçíàþùèé äîïîëíåíèå ÿçûêà L.(0, 1)a(0, 2)aaa(0, 0)b(0, 3)bb b(1, 3)b bb(1, 0)baa(1, 2)aa(1, 1)Òåïåðü ïîñòðîèì äëÿ äàííîãî ïîëíîãî àâòîìàòà, àâòîìàò, ðàñïîçíàþùèé èíâåðòèðîâàííûéRÿçûê L̄ .