7 неделя (1178960)
Текст из файла
Ïóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÇàäàíèå 7Çàäà÷à 1: ßçûê L= ÿâëÿåòñÿ ÿçûêîì âñåõ ñëîâ ñ ðàâíûì ÷èñëîì ñèìâîëîâ aè b.1. Ïîñòðîéòå ìàãàçèííûé àâòîìàò (ÌÀ), ðàñïîçíàþùèé ÿçûêÀâòîìàò M :L= .a, Z0 /aZ0 | a, a/aa | a, a−1 /εq0ε, Z0 /εq1b, Z0 /a−1 Z0 | b, a/ε | b, a−1 /a−1 a−1Àëôàâèò ñòåêàâ ñòåêå íàõîäèòñÿýëåìåíòàΓ = {a, a−1 , Z0 }. Áóäåì ñ÷èòàòü a−1 - îòðèöàòåëüíûì a. Ò.å åñëè3 ýëåìåíòà a−1 , ýòî âñå ðàâíî, ÷òî åñëè áû â ñòåêå íàõîäèëîñü −3a.Äîêàçàòåëüñòâî.• L(M ) ⊆ L=Äëÿ ïðîèçâîëüíîãî ñëîâàω , ïðèíÿòîãî àâòîìàòîì, åãî îáðàáîòêà çàêîí÷èëàñü âq1 , êóäà îí ìîã ïîïàñòü òîëüêî ïåðåéäÿ íà ïîñëåäíåì øàãå èç q0 ε−ïåðåõîäîì:(q0 , ε, Z0 ) ` (q1 , ε, ε). Ðàññìîòðèì íàõîæäåíèå ñëîâà â ñîñòîÿíèè q0 . Åñëè àâòîìàòñ÷èòûâàåò î÷åðåäíóþ áóêâó a, òî îí óâåëè÷èâàåò íà 1 ÷èñëî ýëåìåíòîâ a â ñòåêå(ò.å, åñëè â ñòåêå íåîòðèöàòåëüíîå ÷èñëî ýëåìåíòîâ a, òî îí äîáàâëÿåò åùå îäíóa, à åñëè îòðèöàòåëüíîå, òî óáèðàåò îäíó îòðèöàòåëüíóþ a: a−1 ).
Åñëè àâòîìàòñ÷èòûâàåò î÷åðåäíóþ áóêâó b, òî îí óìåíüøàåò íà 1 ÷èñëî ýëåìåíòîâ a â ñòåêå(ò.å, åñëè â ñòåêå ïîëîæèòåëüíîå ÷èñëî ýëåìåíòîâ a, òî îí óáèðàåò îäíó a, èíà÷å- äîáàâëÿåò îäíó îòðèöàòåëüíóþ a: a−1 ). Òàêèì îáðàçîì, â ñòåêå íàõîäèòñÿ 0ýëåìåíòîâ a òîãäà è òîëüêî òîãäà, êîãäà ñ÷èòàííîå êîëè÷åñòâî a è b ñîâïàäàåò.Òàêèì îáðàçîì, êîãäà áûë ñîâåðøåí ïåðåõîä ïî ε, Z0 â ïðèíèìàþùåå ñîñòîÿíèå,ýòî îçíà÷àëî, ÷òî â ñòåêå 0 ýëåìåíòîâ a, à çíà÷èò, â ñ÷èòàííîì ñëîâå ω êîëè÷åñòâîáóêâ a è b - ñîâïàäàåò. ⇒ ω ∈ L=• L= ⊆ L(M )Äîêàæåì âêëþ÷åíèå ìåòîäîì ñòðóêòóðíîé èíäóêöèè. Äîêàæåì, ÷òî åñëè âñå ñëî-L= äëèíû n è ìåíüøå ðàñïîçíàþòñÿ àâòîìàòîì, òî è ëþáîå ñëîâî èç L äëèíûn + 1 òàê æå ðàñïîçíàåòñÿ àâòîìàòîì.
Áàçà: ε ∈ L= , ε ðàñïîçíàåòñÿ àâòîìàòîì.Ðàññìîòðèì ïðîèçâîëüíîå ñëîâî ω ∈ L= äëèíû n + 1. Ñóùåñòâóåò íåñêîëüêî ïðåäñòàâëåíèé ω :âà1.ω = aU bèëèU ∈ L= .èíäóêöèè U ðàñïîçíàåòñÿω = bU a,Ïî ïðåäïîëîæåíèþãäåàâòîìàòîì, ò.å ïî îêîí÷àíèþåãî îáðàáîòêè â ñòåêå íàõîäèëîñü 0 ýëåìåíòîâa, ïðåäïîñëåäíåé êîíôèãóðàöèåé àâòîìàòà áûëà (q0 , ε, Z0 ), ïîñëåäíåé - (q1 , ε, ε). Åñëè ω = aU b, òî êîíôèãóðàöèåé àâòîìàòà ïîñëå îáðàáîòêè ïîäñëîâà aU áóäåò (q0 , b, aZ0 ), çàòåì` (q0 , ε, Z0 ) ` (q0 , ε, ε), ñëîâî ω ïðèíÿòî àâòîìàòîì.
Àíàëîãè÷íî ω = bU aïðèíèìàåòñÿ àâòîìàòîì: (q0 , bU a, Z0 ) ` (q0 , U a, a−1 Z0 ) `∗ (q0 , a, a−1 Z0 ) `(q0 , ε, Z0 ) ` (q1 , ε, ε)Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACC2.plyus.pavelω = u · v , u, v ∈ L= ñèëó ïðåäïîëîæåíèÿ èíäóêöèè(q0 , u, Z0 ) `∗ (q0 , ε, Z0 ) ` (q1 , ε, ε)(q0 , v, Z0 ) `∗ (q0 , ε, Z0 ) ` (q1 , ε, ε)Òîãäà (q0 , u · v, Z0 ) `∗ (q0 , v, Z0 ) `∗ (q0 , ε, Z0 ) ` (q1 , ε, ε),ò.å ñëîâîωïðèíèìà-åòñÿ àâòîìàòîì.012n+1ω =− ω1 − ω2 − .
. . ωn+1 − . Íî òîãäà ïîÒåîðåìå Âåéåðøòðàññà íàéäåòñÿ òàêîå n, ÷òî ôóíêöèÿ d(n) = |w0n |a − |w0n |b ,ãäå w0n - ñëîâî, ïîëó÷àåìîå èç áóêâ ìåæäó 1 è n ïîçèöèÿìè, ïðèíèìàåò íóëåâîåçíà÷åíèå. À çíà÷èò, ðàçáèòü ω íà äâà ñëîâà (âòîðîå - âîçìîæíî, ε ), îòâå÷àþùèìóñëîâèþ L= ìîæíî.Äðóãèõ ïðåäñòàâëåíèéωíåò, ò.êP.S. Ìîæíî áûëî áû îáîéòèñü è îäíèì ñîñòîÿíèåì, íàïðàâèâ ïåðåõîä ïîíà âåðõóøêå ñòåêà íå âq1 ,εïðèZ0à â ñàìîãî ñåáÿ.
ïîëó÷èëñÿ áû àâòîìàò, ïðèíèìàþùèé ïîïóñòîìó ñòåêó.Çàäà÷à 2: ßçûê Äèêà ñ äâóìÿ òèïàìè ñêîáîê D2 ïîðîæäàåòñÿ ãðàììàòèêîéS → SS | (S) | [S] | ε.1. Ïîñòðîéòå íåäåòåðìèíèðîâàííûé ÌÏ-àâòîìàò, ðàñïîçíàþùèé ÿçûê D2 .2. Ïîñòðîéòå äåòåðìèíèðîâàííûé ÌÏ-àâòîìàò, ðàñïîçíàþùèé ÿçûê D2 , è ïðèâåäèòå äîêàçàòåëüñòâî åãî êîððåêòíîñòè ïî èíäóêöèè.Äëÿ ïðîñòîòû çàïèñè ïåðåîïðåäåëèì àëôàâèò Σ: ¾(¿ = ¾a¿, ¾)¿ = ¾b¿, ¾[¿ = ¾c¿,¾]¿ = ¾d¿. Γ = {a, b, Z0 }. Òàêæå ñèìâîë τ îçíà÷àåò ëþáîé êîíêðåòíûé ñèìâîë èç Γ , ò.åçàïèñü a, τ /aτ ýêâèâàëåíòíà çàïèñè a, a/aa | a, b/ab | a, Z0 , aZ0Àâòîìàò M :a, τ /aτ | c, τ /cτq0b, a/ε | d, c/ε | ε, Z0 /εÄîêàçàòåëüñòâî.• L(M ) ⊆ D2Äëÿ ïðîèçâîëüíîãî ñëîâàω , ïðèíÿòîãî àâòîìàòîì, åãî îáðàáîòêà çàêîí÷èëàñüq0 , à ñòåê îêàçàëñÿ ïóñò.
Ïðè êàæäîì ñ÷èòûâàíèè îòêðûâàþùåé ñêîáêè, ò.å aèëè c, ñîîòâåòñòâóþùèé ñèìâîë êëàäåòñÿ â ñòåê, à ïðè ñ÷èòûâàíèè çàêðûâàþùåéñêîáêè ñîîòâåòñòâóþùèé ñèìâîë îòêðûâàþùåé ñêîáêè çàáèðàåòñÿ èç ñòåêà (äëÿ bçàáèðàåòñÿ a, à äëÿ d çàáèðàåòñÿ c). Òàêèì îáðàçîì, â ïðèíÿòîì ñëîâå êîëè÷åñòâîâîòêðûâàþùèõñÿ è çàêðûâàþùèõñÿ ñêîáîê êàæäîãî òèïà ñîâïàäàåò, âñëåäñòâèåïóñòîòû ñòåêà. Ïî îêîí÷àíèþ ðàáîòû äëÿ êàæäîé îòêðûâàþùåéñÿ ñêîáêè ãäå-òîáûëà (âîçìîæíî, â íåêîððåêòíîì ïîëîæåíèè) åå çàêðûâàþùàÿñÿ ñêîáêàÏîëîìêà àâòîìàòà íå âîçíèêàåò ïðè ñ÷èòûâàíèè îòêðûâàþùèõñÿ ñêîáîê, îíà ìîæåò âîçíèêíóòü òîëüêî ïðè ñ÷èòûâàíèèb è d. Åñëè ñ÷èòûâàåòñÿ b, à â ñòåêå ñâåðõóa, òî àâòîìàò ñëîìàåòñÿ.
Åñëèíåò ñîîòâåòñòâóþùåé åìó îòêðûâàþùåéñÿ ñêîáêèÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelæå ïîëîìêè íå ïðîèçîøëî, òî äëÿ òåêóùåãîêàa,bçàêðûâàåòñÿ ðàíåå îòêðûòàÿ ñêîá-ïðè÷åì â ýòîé ñêîáêå íåò äðóãèõ âíóòðåííèõ íåçàêðûòûõ ñêîáîê (èíà÷å áûñâåðõó ñòåêà íå íàøëîñü áû ïîäõîäÿùåãî a).
Òî÷íî òàêæå è äëÿ d: êîððåêòíîå ïðî÷èòûâàíèådîçíà÷àåò çàêðûòèå ðàíåå îòêðûòîé ñêîáêèc,â çàêðûâàåìîé ñêîáêåíåò âíóòðåííèõ íåçàêðûòûõ ñêîáîê.Òàêèì îáðàçîìω ∈ D2• D2 ⊆ L(M )Äîêàæåì âêëþ÷åíèå ìåòîäîì ñòðóêòóðíîé èíäóêöèè. Äîêàæåì, ÷òî åñëè âñå ñëîâàD2D2äëèíû÷åòíîé äëèíûn+2nè ìåíüøå ðàñïîçíàþòñÿ àâòîìàòîì, òî è ëþáîå ñëîâî èçòàê æå ðàñïîçíàåòñÿ àâòîìàòîì. (Î÷åâèäíî, ÷òî âñå ñëîâà èçèìåþò ÷åòíóþ äëèíó) Áàçà: Ñëîâàïðîèçâîëüíîå ñëîâîω ∈ D2äëèíûëèøü íåñêîëüêî ïðåäñòàâëåíèé1.D2ε, ab, cd ðàñïîçíàþòñÿ àâòîìàòîì. Ðàññìîòðèìn + 2. Èç ãðàììàòèêè ñëåäóåò, ÷òî ñóùåñòâóåòω:ω = cU d, ãäå U ∈ D2 è ðàñïîçíàåòñÿ àâòîìàòîì â ñèëó ïðåäïî(q0 , U, Z0 ) `∗ (q0 , ε, Z0 ) ` (q0 , ε, ε)Òîãäà äëÿ è ω ïðèíèìàåòñÿ àâòîìàòîì: (q0 , aU b, Z0 ) ` (q0 , U b, aZ0 ) `∗ (q0 , b, aZ0 ) `(q0 , ε, Z0 ) ` (q0 , ε, ε) èëè (q0 , cU d, Z0 ) ` (q0 , U d, cZ0 ) `∗ (q0 , d, cZ0 ) ` (q0 , ε, Z0 ) `(q0 , ε, ε)ω = aU bèëèëîæåíèÿ èíäóêöèè:2.ω = u · v,ãäåu, v ∈ D2 . ñèëó ïðåäïîëîæåíèÿ èíäóêöèè(q0 , u, Z0 ) `∗ (q0 , ε, Z0 ) ` (q0 , ε, ε)(q0 , v, Z0 ) `∗ (q0 , ε, Z0 ) ` (q0 , ε, ε)Òîãäà (q0 , u · v, Z0 ) `∗ (q0 , v, Z0 ) `∗ (q0 , ε, Z0 ) ` (q0 , ε, ε),ò.å ñëîâîωïðèíèìà-åòñÿ àâòîìàòîì.Ïîñòðîèì äåòåðìèíîèðîâàííûé àâòîìàòPäëÿ ýòîé çàäà÷è:ε, Z0 /Z0a, Z0 /aZ0 | c, Z0 /cZ0q0q1b, a/ε | d, c/εa, a/aa | a, c/ac | c, a/ca | c, c/cca, τ /aτ | c, τ /cτb, a/ε | d, c/εÄîêàçàòåëüñòâî.• D2 ⊆ L(M )Äîêàæåì âêëþ÷åíèå ìåòîäîì ñòðóêòóðíîé èíäóêöèè.
Äîêàæåì, ÷òî åñëè âñå ñëîâàD2D2äëèíû÷åòíîé äëèíûn+2nè ìåíüøå ðàñïîçíàþòñÿ àâòîìàòîì, òî è ëþáîå ñëîâî èçòàê æå ðàñïîçíàåòñÿ àâòîìàòîì. (Î÷åâèäíî, ÷òî âñå ñëîâà èçèìåþò ÷åòíóþ äëèíó) Áàçà: Ñëîâàε, ab, cdq2D2ðàñïîçíàþòñÿ àâòîìàòîì. Ïðåæäå çà-ìåòèì, ÷òî â ïðèíèìàþùåå ñîñòîÿíèå ìîæíî ïîïàñòü òîëüêî ïóñòûì ñëîâîì, ëèáîèç ñîñòîÿíèÿ q2 , èìåÿ ïóñòîé ñòåê. Ðàññìîòðèì ïðîèçâîëüíîå ñëîâî ω ∈ D2 äëèíûn + 2. Èç ãðàììàòèêè ñëåäóåò, ÷òî ñóùåñòâóåò ëèøü íåñêîëüêî ïðåäñòàâëåíèé ω :Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACC1.plyus.pavelω = cU d, ãäå U ∈ D2 è ðàñïîçíàåòñÿ àâòîìàòîì â ñèëó ïðåäïî(q0 , U, Z0 ) `∗ (q2 , ε, Z0 ) ` (q0 , ε, ε)Òîãäà äëÿ è ω ïðèíèìàåòñÿ àâòîìàòîì: (q0 , aU b, Z0 ) ` (q, U b, aZ0 ) `∗ (q2 , b, aZ0 ) `(q2 , ε, Z0 ) ` (q0 , ε, ε) èëè (q0 , cU d, Z0 ) ` (q1 U d, cZ0 ) `∗ (q2 , d, cZ0 ) ` (q2 ε, Z0 ) `(q0 , ε, ε)ω = aU bèëèëîæåíèÿ èíäóêöèè:2.ω = u · v,ãäåu, v ∈ D2 . ñèëó ïðåäïîëîæåíèÿ èíäóêöèè(q0 , u, Z0 ) `∗ (q2 , ε, Z0 ) ` (q0 , ε, ε)(q0 , v, Z0 ) `∗ (q2 , ε, Z0 ) ` (q0 , ε, ε)Òîãäà (q0 , u · v, Z0 ) `∗ (q2 , v, Z0 ) ` (q0 , v, Z0 ) `∗ (q2 , ε, Z0 ) ` (q0 , ε, ε),ω ïðèíèìàåòñÿ àâòîìàòîì.ò.å ñëîâî• L(M ) ⊆ D2Äîêàæåì âêëþ÷åíèå ïî ñòðóêòóðíîé èíäóêöèè.
Äëÿ ýòîãî ïîéìåì ñìûñë àâòîìàòà. Ðàññìîòðèì ïðîèçâîëüíîå ñëîâîω, ðàñïîçíàâàåìîå àâòîìàòîì. Åãî îáðàáîòêàçàâåðøèëàñü â ñîñòîÿíèè q0 , êóäà ìîæíî ïîïàñòü òîëüêî èç q2 , èìåÿ ïóñòîé ñòåê.Çàìåòèì, ÷òî ïîñëå ïðî÷òåíèÿ îòêðûâàþùåé ñêîáêè ìû îêàæåìñÿ â ñîñòîÿíèèq1 .Òàêæå â ñòåê ïîëîæèòñÿ ñîîòâåòñâóþùàÿ îòêðûâàþùàÿñÿ ñêîáêà.
Ïîñëå ñ÷è-òûâàíèÿ çàêðûâàþùåé ñêîáêè, íàõîäÿñü â ñîñòîÿíèÿõñîñòîÿíèåq2 ,q1èëèq2 ,ìû ïåðåéäåì âèçúÿâ èç ñòåêà ñîîòâåòñòâóþùóþ îòêðûâàþùóþ ñêîáêó. Ñ÷èòàòüçàêðûâàþùóþ ñêîáêó â ñîñòîÿíèèq0íåëüçÿ: âåäü íàõîäÿñü â ýòîì ñîñòîÿíèè,ìû èìååì ïóñòîé ñòåê, à çíà÷èò îòêðûòûõ ñêîáîê íåò. Ïîëó÷èëè, ÷òî ïîñëå ñ÷èòûâàíèÿ îòêðûâàþùèõ ñêîáîê ìû íàõîäèìñÿ â ñîñòîÿíèèq1 ,ïîñëå ñ÷èòûâàíèÿçàêðûâàþùèõ - â q2 , à åñëè ñ÷èòàâ î÷åðåäíóþ çàêðûâàþùóþ ñêîáêó, ìû çàêðûëèâñå ðàíåå îòêðûòûå ñêîáêè, ò.å ñòåê îêàçàëñÿ ïóñò, ìû ïåðåéäåì â q0 , ãäå è íàõîäèëèñü ñ ñàìîãî íà÷àëà ðàáîòû àâòîìàòà.Òåïåðü âèäíî, ÷òî îêàçàâøèñü â ñîñòîÿíèèq0ïîñëå íà÷àëà ðàáîòû àâòîìàòà ìûñ÷èòàëè êîððåêòíóþ ñêîáî÷íóþ çàïèñü - ñëîâî èç ÿçûêà Äèêà.
Òàêèì îáðàçîì,ïðîèçâîëüíîå ñëîâîω,ñ÷èòàííîå àâòîìàòîìω = ω1 · · · ωn ,ãäåωi ∈ D2 , i ≤ n ⇒ω ∈ D2 .Çàäà÷à 3: Ïîñòðîéòå ÌÏ-àâòîìàò, ðàñïîçíàþùèé ÿçûê ïàëèíäðîìîâ L.Àâòîìàòa, Z0 /aZ0 | a, a/aa | a, b/abq0P:a, a/ε | b, b/ε | ε, Z0 /εε, a/a | ε, b/b | ε, Z0 /Z0 | ε, a/ε | ε, b/εq1b, Z0 /bZ0 | b, a/ba | b, b/bbÄîêàçàòåëüñòâî.• L ⊆ L(P )Ëþáîé ïàëèíäðîìωèìååò âèäω = ω1 ω1Rèëèω = ω1 cω1R ,ãäåω1- îäíà èç áóêâ àëôàâèòà.  ïåðâîì ñëó÷àå, ïðî÷èòàåì âñå áóêâû- ëþáîå ñëîâî,ω1 ,cîñòàâàÿñü âñîñòîÿíèèq0 , çàòåì ïåðåéäåì â q1 , ñîõðàíÿÿ ñîñòîÿíèå ñòåêà, è ïðî÷èòàåì ñëîâîω1R , âûáðàñûâàÿ èç ñòåêà ñ÷èòûâàåìûå áóêâû.  ðåçóëüòàòå ðàáîòû àâòîìàòà ñòåêÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCîêàæåòñÿ ïóñòûì è ñëîâîè ïîñëåäóþùóþ áóêâóc,plyus.pavelωïðèìåòñÿ.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
