3 неделя (1178958)
Текст из файла
Ïóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÄîìàøíÿÿ ðàáîòà 3Çàäà÷à 1:Îïðåäåëèì ÿçûê Li = {w | |w| = n, w[n − i] = 1}, òîåñòü â ÿçûê Li âõîäÿò âñå ñëîâà, â êîòîðûõ 1 ñòîèò íà i-îì ìåñòå îòêîíöà1 . Ïîñòðîéòå ÍÊÀ, ðàñïîçíàþùèé ÿçûê L3 . Ïî ïîñòðîåííîìó ÍÊÀïîñòðîéòå ÄÊÀ.Ïîñòðîèì ÍÊÀ, ðàñïîçíàþùèé L3 :ÀâòîìàòA:01q0q1Σq2Σq3Äîêàçàòåëüñòâî.• L(A) ⊆ L3 :∀ω ∈ L(A) óãîîáðàáîòêà çàêîí÷èëàñü â ïðèíèìàþùåì ñîñòîÿíèèq3 . íåãî ìîæíî ïîïàñòü òîëüêî äâóìÿ ïåðåõîäàìè ïî ëþáûì áóêâàìàëôàâèòà èçq1ñîñòîÿíèÿïåðåõîäîì ïî åäèíèöå. Çíà÷èò, òðåòüåé áóêâîé ñ êîíöàñëîâàωq0èÿâëÿåòñÿq21.ñîîòâåòñòâåííî.
Ïîïàñòü âÀ çíà÷èòω ∈ L3 .q1ìîæíî òîëüêî èç ñèëó ïðîèçâîëüíîñòèωïðåä-ëîæåíèå äîêàçàíî.• L3 ⊆ L(A) :∀ω ∈ L3 ω = Σk 1(0|1)(0|1), k ∈ N0 . Ïîñëå îáðàáîòêè ïîäñëîâà Σk àâòîìàò îñòàåòñÿ â ñîñòîÿíèè q0 . Äàëåå ïåðåõîäîì ïî 1 îí îêàçûâàåòñÿ â q1 .Äàëüøå ïåðåõîäîì ïî äâóì ëþáûì áóêâàì àëôàâèòà Σ = {0, 1} àâòîìàò îêàçûâàåòñÿ â ñîñòîÿíèÿõ ñîîòâåòñòâåííî q2 è q3 .  ïðèíèìàþùåìñîñòîÿíèè q3 è çàêàí÷èâàåòñÿ îáðàáîòêà ω , à çíà÷èò ω ïðèíèìàåòñÿàâòîìàòîì ⇒ â ñèëó ïðîèçâîëüíîñòè ω ïðåäëîæåíèå äîêàçàíîL(A) ⊆ L3 , L3 ⊆ L(A) ⇒ L(A) = L31 Âî èçáåæàíèè ïóòàíèöû, ïåðâûé ñ êîíöà ñèìâîë ýòî ïîñëåäíèé ñèìâîë ñëîâà.Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÏîñòðîèì ÄÊÀ àëãîðèòìîì, ðàññêàçàííûì íà ñåìèíàðå:ÀâòîìàòB:0q011q101q21010q4011q3q61q5000q7ÌÑîñò.Q0Q1Q2Q3Q4Q5Q6Q7Ñîñòîÿíèÿ ÍÊÀq0q0 , q1q0 , q1 , q2q0 , q2q0 , q1 , q2 , q3q0 , q2 , q3q0 , q1 , q3q0 , q3Çàäà÷à 3:10Q1Q2Q4Q6Q4Q6Q2Q1Q0Q3Q5Q7Q5Q7Q3Q0Áóäóò ëè ðåãóëÿðíûìè ñëåäóþùèå ÿçûêè?1.L = {a2013n+5 | n = 0, 1, } ∩ {a503k+29 | k = 401, 402, .
. .} ⊆ {a∗ }.2.L2 = {a200n3. ßçûê2+1| n = 1000, 1001, . . .} ⊆ {a∗ }.L3 âñåõ ñëîâ â àëôàâèòå {0, 1}, êîòîðûå ïðåäñòàâëÿþò ÷èñëà âäâîè÷íîé çàïèñè, äàþùèå îñòàòîê äâà ïðè äåëåíèè íà òðè (ñëîâî ÷èòàåòñÿ ñî ñòàðøèõ ðàçðÿäîâ). Íàïðèìåð, 001010 (10102 = 1010 = 3 × 3 + 1) 6∈ L3 ,à 10001 (100012 = 1710 = 5 × 3 + 2) ∈ L3 .Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÏóíêò 2: Ïðåäïîëîæèì, ÷òî ÿçûêL2 - ðåãóëÿðíûé. Òîãäà ïî Ëåììå î íàêà÷êå∃p : ∀ω ∈ L2 : |ω| > p ,→ ω = xyz; |y| > 0; |xy| ≤ p; ∀i ≥ 0, xy i z ∈ L2 .Âñå ñëîâà èç L2 èìåþò âèä am , m = 200n2 + 1; n = 1000, 1001, .
. .. Àçíà÷èò y = am , m ∈ N . Âîçüìåì íåêîòîðîå ôèêñèðîâàííîå ω |ω| =l, ω = al , íî òîãäà ∀i ≥ 0al+im òàêæå ïðèíàäëåæàò ÿçûêó L2 , ÷òîíåâåðíî, ò.ê â L2 êîëè÷åñòâî áóêâ â ñëîâàõ ðàñòåò êâàäðàòè÷íî è ñíåêîòîðîãî ÷èñëà s ws+1 − ws > m, ãäå wi - iîå ñëîâî ïî âîçðàñòàíèþ2(wi = a200(999+i) +1 , i ∈ N ). Çíà÷èò, íàøå ïðåäïîëîæåíèå íåâåðíî, èL2 - íåðåãóëÿðíûé.Ïóíêò 1:Ñïåðâà äîêàæåì, ÷òî â ÿçûêå L1 áåñêîíå÷íîå ÷èñëî ñëîâ è ∀n ∃N>n : aN ∈ L1 .2013n + 5 = 503k + 29 ⇒ 2013n − 503k = 24Âîñïîëüçóåìñÿ àëãîðèòìîì Åâêëèäà:2013 = a, 503 = b: 2013−4·503 = 1 = a−4b ⇒ 24a−96b = 24⇒ ó÷èòûâàÿ çíàê n0 = 24, k0 = 96 ⇒ n = 24+503g, k = 96+2013g ,Ïóñòüà çíà÷èò ïåðåñå÷åíèå ýòèõ äâóõ ìíîæåñòâ äàåò áåñêîíå÷íîå ìíî-∀n ∃N > n : aN ∈ L1 , ò.êL1 = {a48317+503·2013g |g ∈ N }æåñòâî, ïðè÷åìçàäàòü êàêÿçûêL1òåïåðü ìîæíîL1 - ðåãóëÿðíûé.
Òîãäà ïî Ëåììå î íàêà÷êå ∃p : ∀ω ∈L1 : |ω| > p ,→ ω = xyz; |y| > 0; |xy| ≤ p; ∀i ≥ 0, xy i z ∈ L1 . Âñå ñëîâà èç L1 èìåþò âèä am , m = 48317 + 503 · 2013g; g = 1, 2 . . . À çíà÷èò y = am , m ∈ N . Òîãäà, äåéñòâèòåëüíî, âîçüìåì p = 1060856(äëèíà ìèíèìàëüíîãî ñëîâà èç L1 ) ∀ω ∈ L1 : |ω| > p ,→ ω =xyz; |y| = 503 · 2013; |x| = 0; |xy| ≤ p; ∀i ≥ 0, xy i z ∈ L1 . Ò.ê ËåììàÏóñòü ÿçûêî íàêà÷êå ÿâëÿåòñÿ íåîáõîäèìûì, íî íå äîñòàòî÷íûì óñëîâèåìðåãóëÿðíîñòè ÿçûêà, ìû ïîêà íè÷åãî íå ìîæåì ñêàçàòü îL1 .
ÍîL1 = {a(2013×24+5)+503×2013g |g ∈ N } - ðåãóëÿðíûé. Äåéñòâèòåëüíî, L1 ìîæíî ïðåäñòàâèòü êîíêàòåíàöèåéa(2013×24+5) · (a2013 )∗ , ÿâëÿþùåéñÿ ðåãóëÿðíûì ÿçûêîì ïî îïðåëåãêî ïîêàçàòü, ÷òîäåëåíèþ.Ïóíêò 3: Ñëîâà ÿçûêàL3- ÷èñëà â äâîè÷íîé çàïèñè(ïîýòîìó çäåñü è äàëåå ïî-íÿòèÿ ñëîâî è ÷èñëî â äâîè÷íîé çàïèñè ìîæíî ñ÷èòàòü ñèíîíèìàìè).Âñå ýòè ÷èñëà (ω äëèíûn , n ∈ N ), êðîìå 0 è 1, ïîëó÷àþòñÿ èç äðóãèõn − 1) ïðèïèñûâàíèåì ñ÷èñåë äëèíû íà åäèíèöó ìåíüøå (ω 0 äëèíûêîíöà0èëè1.Ðàçáåðåìñÿ â ñóòè ïðèïèñûâàíèÿ ýòèõ öèôð. Ïðèïè-2 (ω = ω 0 × 2), à ïðèïèñûâàíèå1 - äîìíîæåíèå íà 2 è äîáàâëåíèÿ åäèíèöû (ω = ω 0 × 2 + 1). Òåïåðüìû ìîæåì ñêàçàòü è ÷òî ïðîèñõîäèò ñ îñòàòêàìè.
ost(ω) - îñòàòîêïðè äåëåíèè íà 3 ÷èñëà ω . Òîãäà ïðè ïðèïèñûâàíèè öèôðû c ê ω 0ost(ω) = (2 × ost(ω 0 ) + c) mod 3.Ðàññìîòðèì àâòîìàò A, â íåì êàæäå ñîñòîÿíèå qi îçíà÷àåò, ÷òî âíåì çàêàí÷èâàåòñÿ îáðàáîòêà ñëîâà, äàþùåãî i â îñòàòêå ïðè äåëåíèè íà 3, i = 0, 1, 2. Î÷åâèäíî, ÷òî îáðàáîòêà ëþáîãî äâîè÷íîãî ñëîâà çàêàí÷èâàåòñÿ â îäíîì èç ýòèõ ñîñòîÿíèé. Çíàÿ ôîðìóëó ost(ω) =ñûâàíèå0îçíà÷àåò äîìíîæåíèå íàÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavel(2×ost(ω 0 )+c) mod 3 è ïðåäïîëàãàÿ ïóñòîå ñëîâî - íóëåì (ò. å ïåðâûéïåðåõîä èç íà÷àëüíîãî ñîñòîÿíèÿ q0 ïî öèôðå c âåäåò â qc ) çàäàäèì ïîíåé ôóíêöèþ δ :δ(q0 , 0) = q0 ; δ(q0 , 1) = q1δ(q1 , 0) = q2×1+0 = q2 ; δ(q1 , 1) = q(2×1+1) mod 3 = q0δ(q2 , 0) = q(2×2) mod 3 = q1 ; δ(q2 , 1) = q(2×2+1) mod 3 = q2F = {q2 } - ïî óñëîâèþ çàäà÷è.ÀâòîìàòA:01q0q1q21001ÀâòîìàòAâàíèÿñëåäóåò ðåãóëÿðíîñòüAðàñïîçíàåò ÿçûêL3 ïîL3 .ïîñòðîåíèþ, à çíà÷èò èç ñóùåñòâî-Çàäà÷à 4: Ïîñòðîéòå ïî ÍÊÀ Aa, ba, bq0A:ÄÊÀ B :ÌÑîñò.Q0Q1Q2Q3Q4Q5Q6Q7aq1Ñîñòîÿíèÿ ÍÊÀq0q0 , q1q0 , q2q0 , q1 , q3q0 , q1 , q4q0 , q2 , q4q0 , q1 , q3 , q4q0 , q4bq210Q1Q1Q3Q4Q4Q6Q4Q4Q0Q2Q0Q2Q5Q7Q5Q7Àâòîìàòaq3aq4B:Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCbplyus.pavelaaq6abaq0aq1baq2aq3bq4q5bbbq7aÇàäà÷à 6: Ïîñòðîéòå ÊÌÏ-àâòîìàò äëÿ ñëîâà abaaÀâòîìàòbK:aaεaaababbabaabaaba, b• Q = {ε, a, ab, aba, abaa}• q0 = ε• F = {abaa}• δ(ε, a) = a, δ(ε, b) = ε,δ(a, a) = l(aa) = a, δ(a, b) = ab,δ(ab, a) = aba, δ(ab, b) = l(abb) = ε,δ(aba, a) = abaa, δ(aba, b) = l(abab) = ab,δ(abaa, a) = abaa, δ(abaa, b) = abaaÇàäà÷à 7∗ : Äîêàæèòå, ÷òî ÊÌÏ-àâòîìàò äëÿ ñëîâà ω ðàñïîçíà-åò ÿçûê Σ∗ ωΣ∗Îïðåäåëèì è äîêàæåì ñìûñë ñîñòîÿíèé àâòîìàòà ÊÌÏ äëÿ ñëîâàÎòìåòèì, ÷òî ∀i = 0 .
. . |ω| ∃ ñîñòîÿíèå ω[0, i].•ω.∀i = 0 . . . |ω| − 1 íàõîæäåíèå â ñîñòîÿíèè ω[0, i] îçíà÷àåò,i áóêâ, ñîâïàäàþùèõ ñ ïåðâûìè iáóêâàìè ω , è íå áîëüøå (ò. å íè äëÿ êàêîãî k > i ïîñëåäíèå k áóêâ íåñîâïàäàþò ñ ïåðâûìè áóêâàìè ω ).Çàìåòèì, ÷òî÷òî íà êîíöå âõîäíîãî ñëîâà åñòüÄîêàçàòåëüñòâî.Áàçà: â íà÷àëå ðàáîòû ìû íàõîäèìñÿ âε, è åñëèc = ω[1]bàâòîìàòÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCïåðåõîäèò âω[0, 1],à åñëèplyus.pavelc 6= ω[1]àâòîìàò îñòàåòñÿ âØàã: Ïóñòü äëÿ ïðîèçâîëüíîãî ñëîâàïåðâûìèiáóêâàìèâ ñîñòîÿíèèωpïîñëåäíèåiε = l(c).áóêâ ñîâïàäàþò ñ, è â ñèëó ïðåäïîëîæåíèÿ èíäóêöèè íàõîäèòñÿω[0, i].Åñëè íà âõîä ïîñòóïàåò áóêâà c, ñîâïàäàþùàÿ ñî ñëåäóþùåé áóêâîéω (c = ω[i + 1]), òî ïî óñëîâèþ àâòîìàò ïåðåõîäèò â ñîñòîÿíèåω[i + 1].
Ýòî äåéñòâèòåëüíî âåðíî, òàê êàê íà êîíöå p òåïåðü i + 1(è íå áîëüøå, ÷åì i + 1) ïåðâûõ áóêâ èç ω .Åñëè íà âõîä ïîñòóïàåò áóêâàc, íå ñîâïàäàþùàÿ ñî ñëåäóþùåéω (c 6= ω[i + 1]), òîãäà ïî óñëîâèþ àâòîìàò ïåðåõîäèò âñîñòîÿíèå l(w[0, i]c). È ýòîò ïåðåõîä êîððåêòåí, òàê êàê òåïåðüïîñëåäîâàòåëüíîñòü áóêâ èç ω ïðåðâàëàñü è íàäî èñêàòü, ñêîëüêîòåïåðü, ñ ó÷åòîì ïîñëåäíåé c, ïåðâûõ áóêâ èç ω íà êîíöå p. Ïîëó÷åííîå ñëîâî pc = xw[0, i]c = x · l(w[0, i]c) · yc = xz · l(w[0, i]c), ãäåx, y, z - ïîäñëîâà p - äåéñòâèòåëüíî, íà êîíöå ïîëó÷åííîãî ñëîâàïîäñëîâî l(w[0, i]c), ñîâïàäàþùåå ñ íà÷àëîì ñëîâà ω , è l(w[0, i]c)- ìàêñèìàëüíî äëèííîå ñëîâî ïî îïðåäåëåíèþ ôóíêöèè l.áóêâîéÒàêèì îáðàçîì ïðè ëþáîé ïîñëåäóþùåé âõîäÿùåé áóêâå ñâîéñòâà ñîñòîÿíèé ñîõðàíÿþòñÿ.•Òàê êàê ÊÌÏ àâòîìàò ÿâëÿåòñÿ âñþäóîïðåäåëåííûì, òî ïðè ëþáîìâõîäÿùåì ñëîâå àâòîìàò íàõîäèòñÿ â íåêîòîðì ñîñòîÿíèè.
Äîêàæåì,÷òî îáðàáîòêà ëþáîãî ñëîâà, êîòîðîå îêàí÷èâàåòñÿ íà ïåðâûåi áóêâ ωω[0, i]. Ïðåäïîëîæèì, ÷òî ýòî íå òàê, ò.å∃p = xω[0] . . . ω[i], i = 0 . . . n ,→ îáðàáîòêà p çàêîí÷èëàñü â ñîñòîÿíèèw[0, k], k 6= i, k = 0 . . . n. Íî òîãäà íà êîíöå p ðîâíî k 6= i ïåðâûõ áóêâèç ω , ÷òî ïðîòèâîðó÷èò âûáîðó p ⇒ íàøå ïðåäïîëîæåíèå íåâåðíî èîáðàáîòêà ëþáîãî ñëîâà, êîòîðîå îêàí÷èâàåòñÿ íà ïåðâûå i áóêâ ω ,çàêàí÷èâàåòñÿ â ñîñòîÿíèè ω[0, i]., çàêàí÷èâàåòñÿ â ñîñòîÿíèèÎñòàëîñü òîëüêî ðàçîáðàòüñÿ ñ ïîñëåäíèì ïðèíèìàþùèì ñîñòîÿíèåì ω[0, n],äëÿ íåãî âåðíî ïîñëåäíåå äîêàçàòåëüñòâî.- ïîäñëîâàp.Îáðàáîòêàxω∀p ∈ Σ∗ ωΣ∗ , p = xωy ,ãäåçàêîí÷èòñÿ â ïðèíèìàþùåì ñîñòîÿíèèx, ω, yω[0, n]ïî ðàíåå äîêàçàííîìó.
Íî äàëåå ïðè ëþáûõ âõîäÿùèõ áóêâàõ, ò.å ïðè ëþáîìy àâòîìàò îñòàåòñÿΣ∗ ωΣ∗ ⊆ L(KM P )â ïðèíèìàþùåì ñîñòîÿíèè⇒ p ∈ L(KM P ) ⇒È îáðàòíî, ò. ê â ïðèíèìàþùåå ñîñòîÿíèå ìîæíî ïîïàñòü èç äðóãîãî ñîñòî-ω[0, n − 1], äëÿ âñåõ ñëîâ, íàõîäÿùèõñÿ â ýòîì ñîñòîÿíèè ïîñëåäíèån − 1 áóêâ ÿâëÿþòñÿ ïåðâûìè n − 1 ñëîâà ω , à çíà÷èò ïåðåõîä â ω[0, n]ïî c = w[n] ñëîâó ïðèäàåò ñâîéñòâî ÿçûêà. Ïåðåõîä ïî ïåòëå â êîíå÷íîìÿíèÿñîñòîÿíèè ïî ëþáîé áóêâå ÿçûêà òàêæå ñîõðàíÿåò åãî ñâîéñòâî.
Çíà÷èò,L(KM P ) ⊆ Σ∗ ωΣ∗ ⇒ L(KM P ) = Σ∗ ωΣ∗Çàäà÷à 8: Ïðèâåäèòå ïðîòîêîë ðàáîòû ÊÌÏ-àëãîðèòìà ïðè ïî-èñêå ïîäñëîâàabba â ñëîâå abbbababbab.Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÄîïèøåì ê ñëîâó abbbababbab ñëîâî abba# è âûïîëíèì àëãîðèòìlen = 0; i = 1; l[i + 1] = l[1 + 1] := 0;00∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅len = 0; i = 2; l[i + 1] = l[2 + 1] := 0;000∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅len = 0; i = 3; l[i + 1] = l[3 + 1] := len + 1 = 0 + 1;0001∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅len = 1; i = 4; len := l[1] = 0; l[i + 1] = l[4 + 1] := 0;00010∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅len = 0; i = 5; l[i + 1] = l[5 + 1] := len + 1 = 0 + 1;000101∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅len = 1; i = 6; l[i + 1] = l[6 + 1] := len + 1 = 1 + 1;0001012∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅len = 2; i = 7; l[i + 1] = l[7 + 1] := len + 1 = 2 + 1;00010123∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅len = 3; i = 8; len := l[3] = 0; l[i + 1] = l[8 + 1] := 0;000101230∅ ∅ ∅ ∅ ∅ ∅ ∅len = 0; i = 9; l[i + 1] = l[9 + 1] := len + 1 = 0 + 1;0001012301∅ ∅ ∅ ∅ ∅ ∅len = 1; i = 10; l[i + 1] = l[10 + 1] := len + 1 = 1 + 1;00010123012∅ ∅ ∅ ∅ ∅len = 2; i = 11; len := l[2] = 0; l[i + 1] = l[11 + 1] := len + 1 = 0 + 1;000101230121∅ ∅ ∅ ∅len = 1; i = 12; l[i + 1] = l[12 + 1] := len + 1 = 1 + 1;0001012301212∅ ∅ ∅len = 2; i = 13; l[i + 1] = l[13 + 1] := len + 1 = 2 + 1;00010123012123∅ ∅len = 3; i = 14; l[i + 1] = l[14 + 1] := len + 1 = 3 + 1;000101230121234∅len = 4; i = 15; len := l[4] = 1; l[i + 1] = l[15 + 1] := len + 1 = 1 + 1;000101230Ïîäñëîâî íàéäåíî, òàê êàê â121234ÊÌÏ215 ÿ÷åéêå ñòîèò ÷èñëî 4, ðàâíîå äëèíå ñëîâàabbaÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ Ïðîãðàììèðîâàíèÿ.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
