8 неделя (8 Задание)

Ïóáëè÷íàÿ ðåäàêöèÿ (3) / ACCplyus.pavelÇàäàíèå 8Ñïèñîê èçìåíåíèé:Èñïðàâëåíà îïå÷àòêà â àâòîìàòå äëÿ 5îé çàäà÷èÈñïðàâëåíî íåñêîëüêî îïå÷àòîê â 1 çàäà÷å (áûëî ìíîãî èñïîëüçîâàíèé A è B âìåñòîM è A ñîîòâåòñòâåííî, ò.ê çà îñíîâó áûëî âçÿòî ìîå æå ðåøåíèå 5 çàäà÷è Âòîðîãîçàäàíèÿ)Çàäà÷à 1:Ïîêàæèòå, ÷òî ÊÑ-ÿçûêè çàìêíóòû îòíîñèòåëüíî ïåðåñå÷åíèÿ ñL ∈ CF L, R ∈ REG, òî L ∩ R ∈ CF L.Ïîñòðîèì ÌÏ-àâòîìàò P , ðàñïîçíàþùèé ïåðåñå÷åíèå L è R ïî ÌÏ-àâòîìàòó Mäëÿ L, ïðèíèìàþùåìó ïî äîïóñêàþùåìó ñîñòîÿíèþ, è äåòåðìèíèðîâàííîìó àâòîìàòóA äëÿ R ñëåäóþùèì îáðàçîì:ðåãóëÿðíûìè. Òî åñòü, åñëè• QP = QM × QA ;• q0P = (q0M , q0A );• ΓP = ΓM ;• ∀σ ∈ Σ ∀τ ∈ Γ : δP ((qA , qB ), σ, τ ) = (δM (qA , σ, τ ), δA (qB , σ));• FP = FM × FA ýòîé çàäà÷å áóäåì ïðåäñòàâëÿòü ñîñòîÿíèÿ àâòîìàòà P ïàðàìè êîîðäèíàò, ò.åq0P = (q0M , q0A ) = q00 , ãäå q0M - ïåðâàÿ êîîðäèíàòà, à q0A - âòîðàÿ êîîðäèíàòà.Çàìåòèì, ÷òî íà ïåðâîì ìåñòå ñòîÿò òîëüêî ñîñòîÿíèÿ èç ïåðâîãî àâòîìàòà M , à íàâòîðîì - òîëüêî ñîñòîÿíèÿ èç àâòîìàòà A (ïî îïðåäåëåíèþ äåêàðòîâà ïðîèçâåäåíèÿ).Ôóíêöèÿ ïåðåõîäîâ çàäàíà êàê ∀σ ∈ Σ ∀τ ∈ Γ : δP ((qM , qA ), σ, τ ) = (δM (qM , σ, τ ), δA (qA , σ)).Ò.å âî âðåìÿ ïåðåõîäîâ íà ïåðâóþ êîîðäèíàòó íèêàê íå âëèÿåò âòîðàÿ, à íà âòîðóþ ïåðâàÿ (òàê êàê ñòåê èñïîëüçóåòñÿ òîëüêî ïåðâîé êîîðäèíàòîé, à âòîðàÿ ñòåê íå èñïîëüçóåò è íå ïîðòèò åãî).

Òàêèì îáðàçîì, àâòîìàò P ìîæíî ñ÷èòàòü è àâòîìàòîì äëÿ M ,ïðîñòî íå ðàçëè÷àÿ âòîðûå êîîðäèíàòû, ñ÷èòàÿ äëÿ êàæäîãî ôèêñèðîâàííîãî qn ∈ QM¾ðàâíûìè¿ ñîñòîÿíèÿ (qn , qk ) ∀qk ∈ QA . Àíàëîãè÷íî ìîæíî íå ðàçëè÷àòü è ïåðâûå êîîðäèíàòû ñîñòîÿíèé, ïîëó÷àÿ àâòîìàò A: ∀qk ∈ QA (qn1 , qk ) = (qn2 , qk )∀qn1 , qn2 ∈ QM .Ìîæíî ïðåäïîëîæèòü, ÷òî âîçíèêàåò ïðîáëåìà, êîãäà äëÿ îäíîãî èç àâòîìàòîâ ôóíêöèÿ ïåðåõîäîâ íå îïðåäåëåíà â íåêîòîðîì ñîñòîÿíèè äëÿ íåêîòîðîãî ïåðåõîäà, à äëÿâòîðîãî îïðåäåëåíà. Íî íà ñàìîì äåëå ïðîáëåìû íåò. Äëÿ ñëó÷àÿ L(M ) ∩ L(A) âñå îñòàåòñÿ â íîðìå, òàê êàê àâòîìàò P ìîæåò ëîìàòüñÿ, åñëè ñëîâî íå ïðèíàäëåæèò îäíîìóèç ÿçûêîâ L(M ) èëè L(A), ÷òî îí è äåëàåò.Âçÿâ íà÷àëüíîå ñîñòîÿíèå äëÿ F q00 = (q0M , q0A ), ñòåê - ïóñò, ìû îáåñïå÷èâàåì êîððåêòíûé ñòàðò èç íà÷àëüíûõ ñîñòîÿíèé äëÿ êàæäîãî àâòîìàòà M è A.Ó÷èòûâàÿ âûøåñêàçàííîå, åñëè îáðàáîòêà ñëîâà w çàêîí÷èëàñü â ñîñòîÿíèè, ãäåïåðâàÿ êîîðäèíàòà ÿâëÿåòñÿ êîíå÷íûì ñîñòîÿíèåì äëÿ M , òî w ∈ L(M ) è îáðàòíî,åñëè w ∈ L(M ) òî åãî îáðàáîòêà â àâòîìàòå P çàêîí÷èòñÿ â ñîñòîÿíèè ñ ïåðâîé êîîðäèíàòîé - êîíå÷íûì ñîñòîÿíèåì M .

È åñëè îáðàáîòêà w çàêîí÷èëàñü â ñîñòîÿíèè, ãäåâòîðàÿ êîîðäèíàòà ÿâëÿåòñÿ êîíå÷íûì ñîñòîÿíèåì äëÿ A, òî w ∈ L(A) è îáðàòíî, åñëèw ∈ L(A) òî åãî îáðàáîòêà â àâòîìàòå P çàêîí÷èòñÿ â ñîñòîÿíèè ñî âòîðîé êîîðäèíàòîéÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (3) / ACCplyus.pavel- êîíå÷íûì ñîñòîÿíèåì A.Òàêèì îáðàçîì, åñëè îáå êîîðäèíàòû êîíå÷íîãî ñîñòîÿíèÿ ÿâëÿþòñÿ êîíå÷íûìè ñîñòîÿíèÿìè äëÿ ñîîòâåòñâåííî M è A, òî àâòîìàò P ðàñïîçíàåò ïåðåñå÷åíèå ÿçûêîâ äëÿM è A, ò.å L(M ) ∩ L(A).Çàäà÷à 3:Äîêàæèòå, ÷òî ÿçûêL = {w | |w|a = |w|b = |w|c } ⊆ {a, b, c}∗íåÿâëÿåòñÿ ÊÑ-ÿçûêîì.Ïðåäïîëîæèì, ÷òî L ÊÑ-ÿçûê, òîãäà äëÿ íåêòîðîãî ÷èñëà p ñïðàâåäëèâà ëåììàî íàêà÷êå. Âîçüìåì ñëîâî ω = ap bp cp ∈ L.

Òîãäà ñóùåñòâóåò åãî ðàçáèåíèå ω = xuyvz ,ïðè÷åì uyv ñîñòîèò ëèáî èç îäèíàêîâûõ áóêâ (al èëè bl èëè cl ), èëè èìååò âèä al brèëè bl cr (ò.ê äëèíà uyv îãðàíè÷åíà p, òî âñåõ òðåõ áóêâ îíî ñîäåðæàòü íå ìîæåò) ⇒uv - ñëîâî, íå ñîäåðæàùåå õîòÿ áû îäíîé èç áóêâ a èëè c. Äëÿ îïðåäåëåííîñòè ïóñòüýòî áóäåò c [a]. Òîãäà âçÿâ i = 0 ïîëó÷àåì ñëîâî ω0 = ap−l bp−r cp [ω0 = ap bp−l cp−r ],êîòîðîå ïî ëåììå î íàêà÷êå ïðèíàäëåæèò L, íî â ñèëó l + r ≥ 1 ⇒ ω0 ∈/ L. Ïîëó÷èëèïðîòèâîðå÷èå ⇒ L íå ÿâëÿåòñÿ ÊÑ-ÿçûêîì.Çàäà÷à 4: Âåðíî ëè, ÷òî ÿçûê L = Σ∗ \ {an bn cn | n ≥ 0} ñîâïàäàåò ñ ÿçûêîìP = {ai bj ck | i 6= j ∨ i 6= k}∗ .Íåò, íåâåðíî. Ïîêàæåì, ÷òî abc ïîðîæäàåòñÿ ÿçûêîì P .

abc = a1 b0 c0 a0 b1 c0 a0 b0 c0 .a1 b0 c0 , a0 b1 c0 , a0 b0 c1 ∈ {ai bj ck | i 6= j ∨ i 6= k} ïîýòîìó ¾ñêëåèâ¿ èõ çâåçäî÷êîé Êëèííèïîëó÷èì abc ∈/ L.Çàäà÷à 5:Âåðíî ëè, ÷òî ÿçûê{an bm bn cm | n, m ≥ 0}ÿâëÿåòñÿ ÊÑ-ÿçûêîì? ñëó÷àå ïîëîæèòåëüíîãî îòâåòà ïîñòðîèòü ÊÑ-ãðàììàòèêó èëè ÌÏ-àâòîìàò äëÿäàííîãî ÿçûêà.Ïîñòðîèì ÌÏ-àâòîìàò M , ðàñïîçíàþùèé ÿçûê L ïî ïóñòîìó ñòåêó:a, Z0 /aZ0 | a, a/aa | ε, Z0 /εq0b, Z0 /a−1 Z0 | b, a−1 /a−1 a−1 | b, a/ε | ε, Z0 /εb, Z0 /a−1 | b, a/εq1c, a−1 /ε | ε, Z0 /εc, a−1 /εÀëôàâèò ñòåêà Γ = {a, a−1 , Z0 }.

Áóäåì ñ÷èòàòü a−1 - îòðèöàòåëüíûì a. Ò.å åñëè â ñòåêåíàõîäèòñÿ 3 ýëåìåíòà a−1 , ýòî âñå ðàâíî, ÷òî åñëè áû â ñòåêå íàõîäèëîñü −3 ýëåìåíòàa.Äîêàçàòåëüñòâî.• L(M ) ⊆ LÄëÿ ïðîèçâîëüíîãî ñëîâà ω , ïðèíÿòîãî àâòîìàòîì, åãî îáðàáîòêà çàêîí÷èëàñü âq1 èëè q2 .1. ω áûëî ïðèíÿòî ïî ïóñòîìó ñòåêó â q0 . q0 ìîæíî òîëüêî ñ÷èòûâàòü a, ïðè÷åì â ñòåê òîãäà áóäóò äîáàâëÿòüñÿñèìâîëû, ëèáî ïî b ïåðåéòè â ñîñòîÿíèå q1 , ëèáî ïðèíÿòü ñëîâî ïî ïóñòîìóñòåêó.

Çíà÷èò áóêâ a ñ÷èòàíî íå áûëî, ω = ε = a0 b0 b0 c0 ∈ L2. ω áûëî ïðèíÿòî ïî ïóñòîìó ñòåêó â q1 .Òîãäà â q1 àâòîìàò ìîã ïîïàñòü òîëüêî èç q0 ïåðåõîäîì ïî b, óáðàâ èç ñòåêà÷èòàííóþ îäíó a (óáðàâ èç ñòåêà a, åñëè îíè åñòü, ëèáî äîáàâèòü a−1 åñëèÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ Ïðîãðàììèðîâàíèÿq2Ïóáëè÷íàÿ ðåäàêöèÿ (3) / ACCplyus.pavelíà âåðøèíå ñòåêà Z0 ).

Ñèìâîëû a âñå ñ÷èòûâàþòñÿ òîëüêî â ñîñòîÿíèè q0 ,è âñå îíè êëàäóòñÿ â ñòåê. À â q1 ñ÷èòûâàþòñÿ b è âûíèìàþòñÿ èç ñòåêà ïîa íà êàæäûé ñ÷èòàííóþ b (íå çàáûâàåì î íàëè÷èè îòðèöàòåëüíûõ a, åñëèâñå a â ñòåêå çàêîí÷èëèñü, ïîä èõ âûíèìàíèåì ïîäðàçóìåâàåòñÿ äîáàâëåíèåa−1 ). Òàêèì îáðàçîì, åñëè ñòåê îêàçàëñÿ ïóñòûì, ýòî çíà÷èò, ÷òî ω = an bn =an bn b0 c0 ∈ L3. ω áûëî ïðèíÿòî ïî ïóñòîìó ñòåêó â q2 .Òîãäà â q2 àâòîìàò ìîã ïîïàñòü òîëüêî èç q1 ïåðåõîäîì ïî c, äîáàâèâ â ñòåêîäíó a ê óæå èìåþùåìñÿ îòðèöàòåëüíûì a â ñòåêå. Ìû óæå çíàåì, ÷òî âñîñòîÿíèè q0 ñ÷èòûâàþòñÿ a è îíè êëàäóòñÿ â ñòåê, â q1 ñ÷èòûâàþòñÿ b èa èç ñòåêà âûíèìàþòñÿ.  ñîñòîÿíèè q2 ñ÷èòûâàþòñÿ ñèìâîëû c, à â ñòåêåóáèðàþòñÿ îòðèöàòåëüíûå a (a−1 ) íà êàæäóþ ñ÷èòàííóþ c. Òàêèì îáðàçîì,åñëè ñòåê îêàçàëñÿ ïóñòûì, ýòî çíà÷èò, ÷òî ω = an bm ck , m > n, n + k = m, ò.åω = an bn+m cm = an bm bn cm ∈ L• L ⊆ L(M )Ïîêàæåì, ÷òî àâòîìàò ðàñïîçíàåò ïðîèçâîëüíîå ω ∈ L: ω = an bn+m cm .Ïóñòü n > 0.

Ñ÷èòûâàåì â ñîñòîÿíèè q0 n áóêâ , ïîñëå ýòîãî â ñòåêå íàõîäèòñÿ n a.Ñ÷èòûâàåì áóêâó b, ïåðåõîäèì â q1 è óáèðàåì èç ñòåêà îäíó a. Çàòåì ñ÷èòûâàåìn − 1 áóêâó b, ïîñëå ÷åãî â ñòåêå îêàçûâàåòñÿ òîëüêî Z0 .Åñëè m > 0, ñ÷èòûâàåì åùå m áóêâ b, ïîñëå ÷åãî â ñòåêå îêàçûâàåòñÿ m ñèìâîëîâa−1 . Çàòåì ñ÷èòûâàåì áóêâó c, ïåðåõîäèì â q2 è óáèðàåì èç ñòåêà îäíó a−1 . Ñ÷èòàåì îñòàâøèåñÿ m − 1 áóêâ c, ïîñëå ÷åãî ñòåê îêàæåòñÿ ïóñò (òîëüêî Z0 ), óáåðåìèç ñòåêà Z0 è ïðèìåì ñëîâî.Åñëè m = 0, òî ïðîñòî óáåðåì èç ñòåêà Z0 è ïðèìåì ñëîâî.Åñëè n = 0, m > 0, òî ñ÷èòûâàåì áóêâó b, ïåðåõîäèì â q1 è äîáàâëÿåì â ñòåê îäíóa−1 . Ñ÷èòûâàåì îñòàâøèåñÿ m − 1 b, ïîëó÷èëè â ñòåêå m ñèìâîëîâ a−1 .

Çàòåìñ÷èòûâàåì áóêâó c, ïåðåõîäèì â q2 è óáèðàåì èç ñòåêà îäíó a−1 . Ñ÷èòàåì îñòàâøèåñÿ m − 1 áóêâ c, ïîñëå ÷åãî ñòåê îêàæåòñÿ ïóñò (òîëüêî Z0 ), óáåðåì èç ñòåêàZ0 è ïðèìåì ñëîâî.Åñëè n = 0, m = 0, òî â ñîñòîÿíèè q0 óáåðåì Z0 è ïðèìåì ñëîâî. ñèëó ïðîèçâîëüíîñòè ω âêëþ÷åíèå äîêàçàíî.Çàäà÷à 6:Äîêàæèòå, ÷òî ÿçûêL = {w | w = uu, u ∈ Σ∗ }, Σ = {a, b},íåÿâëÿåòñÿ ÊÑ-ÿçûêîì.Ïðåäïîëîæèì, ÷òî L ÊÑ-ÿçûê, òîãäà äëÿ íåêòîðîãî ÷èñëà p ñïðàâåäëèâà ëåììàî íàêà÷êå. Âîçüìåì ñëîâî ω = ap bp ap bp .

Òîãäà ñóùåñòâóåò åãî ðàçáèåíèå ω = xuyvz ,ïðè÷åì uyv ñîñòîèò ëèáî èç îäèíàêîâûõ áóêâ (al èëè bl ), èëè èìååò âèä al br , èëè br al .Òîãäà u è v ìîãëè èìåòü òå æå âèäû.• u = al , v = arÏðè i = 0, ïîëó÷àåì ñëîâà âèäà ap−l−r bp ap bp èëè ap bp ap−l−r bp , îíè íå ïðåäñòàâèìû â âèäå êâàäðàòîâÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (3) / ACCplyus.pavel• u = bl , v = brÏðè i = 0, ïîëó÷àåì ñëîâà âèäà abp−l−r ap bp èëè ap bp ap bp−l−r , îíè íå ïðåäñòàâèìûâ âèäå êâàäðàòîâ• u = al , v = br èëè u = br , v = alÏðè i = 0, ïîëó÷àåì ñëîâà âèäà ap−l bp−r ap bp , ap bp ap−l bp−r èëè ap bp−r ap−l bp , êîòîðûå íå ïðåäñòàâèìû â âèäå êâàäðàòîâ.• u = al , v = am brÏðè i = 0, ïîëó÷àåì ñëîâî âèäà ap−l−m bp−r ap bp èëè ap bp ap−l−m bp−r , êîòîðûå íåïðåäñòàâèìû â âèäå êâàäðàòîâ.• Àíàëîãè÷íî u = am br , v = bl ; u = br , v = bm al ; u = bm ar , v = alÏðè i = 0, ïîëó÷àåì ñëîâà âèäà ap−m bp−r−l ap bp , èëè ap bp ap−m bp−r−l , èëè ap bp−r−m ap−l bp ,èëè ap bp−m ap−r−l bp , êîòîðûå íå ïðåäñòàâèìû â âèäå êâàäðàòîâ.⇒ ïîëó÷èëè ïðîòèâîðå÷èå ⇒ L - íå ÿâëÿåòñÿ ÊÑ-ÿçûêîìÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ Ïðîãðàììèðîâàíèÿ.