8 неделя (1178961)
Текст из файла
Ïóáëè÷íàÿ ðåäàêöèÿ (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 - íå ÿâëÿåòñÿ ÊÑ-ÿçûêîìÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ Ïðîãðàììèðîâàíèÿ.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
