Iv_task7 (1178910)
Текст из файла
Ñåðãåé Èâàíû÷åâÃðóïïà 376ÔÓÏÌ ÌÔÒÈsergeyivanychev@gmail.comvk.com/ivanychevsergey+79104577995Âåðñèÿ 1.0Çàäàíèå 7Êîíòåêñòíî-ñâîáîäíûå ÿçûêè è ìàãàçèííûå àâòîìàòû1Óïðàæíåíèå 11.1w ∈ L ⇒ w ∈ L(A), w ∈ L(B)Ïðèâåäåì äèàãðàììû àâòîìàòîâ èç çàäàíèÿ íèæåa, Z0 /aZ0 a, a/aab, a/εb, a/εq0ε, Z0 /εq1q2Äàííûé àâòîìàò ÿâëÿåòñÿ äîïóñêàþùèì ïî çàâåðøàþùåìó ñîñòîÿíèþ (A).a, Z0 /aZ0 a, a/aaq0b, a/ε ε, Z0 /εb, a/εq1Äàííûé àâòîìàò ÿâëÿåòñÿ äîïóñêàþùèì ïî ïóñòîìó ñòåêó (B ).Ïóñòüw ∈ L : w = an bn ,òîãäà äëÿ ïåðâîãî àâòîìàòà èìååì(q0 , an bn , Z0 ) ` (q0 , an−1 bn , aZ0 ) ` (q0 , an−2 bn , aaZ0 ) `∗ (q0 , bn , an Z0 ) `` (q1 , bn−1 , an−1 Z0 ) `∗ (q1 , ε, Z0 ) ` (q2 , ε, ε)(1)Ãäå çàêëþ÷èòåëüíîå ñîñòîÿíèå àâòîìàòà ÿâëÿåòñÿ ïðèíèìàþùèì, òî åñòü àâòîìàò ïðèíèìàåò ñëîâà èçL.
Ñòîèò îòìåòèòü, ÷òî ñâåðõó ïðèâåäåí âèä ïîñëåäîâàòåëüíîñòè êîíôèãóðàöèé1äëÿ êàê ìèíèìóìn > 2.  ïðîòèâíîì ñëó÷àå ïîíÿòíî, ÷òî íåêîòîðûõ áèíàðíûõ îòíîøåíèén = 1).â ïîñëåäîâàòåëüíîñòè íå áóäåò (íàïðèìåð, òðåòüåé êîíôèãóðàöèè ïðèÀíàëîãè÷íî, äëÿ âòîðîãî àâòîìàòà èìååì(q0 , an bn , Z0 ) ` (q0 , an−1 bn , aZ0 ) ` (q0 , an−2 bn , aaZ0 ) `∗ (q0 , bn , an Z0 ) `` (q1 , bn−1 , an−1 Z0 ) `∗ (q1 , ε, Z0 ) ` (q1 , ε, ε)Ãäå ïîñëå îáðàáîòêè ñëîâà èçèçL1.2L(2)ñòåê ïóñò, òî åñòü ñëîâî ïðèíÿòî. Äîêàæåì, ÷òî ñëîâà íåíå áóäóò ïðèíÿòû àâòîìàòîì.w 6∈ L ⇒ w 6∈ L(A), w 6∈ L(B)Äîêàæåì, ÷òî ñëîâà, íå ëåæàùèå â ÿçûêåâà ñîäåðæàò â ñåáå ïîäñëîâîL0 = a∗ b∗ íå áóäóò ïðèíÿòû àâòîìàòîì. Òàêèå ñëî-ba.
Òîãäà ðàññìîòðèì îáðàáîòêó äàííîãî ïîäñëîâà àâòîìàòîì.q0Ïóñòü äàííîå ïîäñëîâî ïîïàëîñü, êîãäà àâòîìàò íàõîäèëñÿ â ñîñòîÿíèè(q0 , w, Z0 ) `∗ (q0 , baw0 , α)Òîãäà êàæäûé èç àâòîìàòîâ ëîìàåòñÿ íà ýòîì ïîäñëîâå, òàê êàê ëèáî íåò îòîáðàæåíèÿq1 , òàê êàêq1 , òàê êàê èça,â ñîñòîÿíèåâåðõóøêà ñòåêà íåñîñòîÿíèèíåãî íåò êàêîãî-ëèáî îòîáðàæåíèÿ ïî ýòîé áóêâå. ñëó÷àå, åñëè ïîäñëîâîbaëèáî ïîñëå îáðàáîòêè áóêâûâñòðåòèëîñü â ñîñòîÿíèèq1 ,Òàêèì îáðàçîì àâòîìàò ðàñïîçíàåò òîëüêî ñëîâà èçL0q1íåò îòîáðàæåíèÿ ïî áóêâå.Ñâîéñòâî äàííîãî àâòîìàòà çàêëþ÷àåòñÿ â òîì, ÷òî ïðè îòîáðàæåíèè ïî áóêâåáóêâaâ ñòåêå óâåëè÷èâàåòñÿ íà 1, à ïðè îòîáðàæåíèè ïîàâòîìàòàBâ íîâîìòî àâòîìàò òàêæå ëîìàåòñÿ, òàêêàê íè èç îäíîãî èç ñîñòîÿíèé, â êîòîðûå ìîæíî ïåðåéòè èça.aba êîëè÷åñòâî óìåíüøàåòñÿ íà 1.
 ñëó÷àåèìååì, ÷òî, òàê êàê ñëîâî ïðèíèìàåòñÿ ïðè ïóñòîì îñòàâøåìñÿ ââîäå è ñòåêå,òî êîëè÷åñòâî áóêâbèaâ ïðèíèìàåìûõ ñëîâàõ äîëæíî áûòü ðàâíûì, ÷òî â ñî÷åòàíèèñ ïðåäûäóùèì àáçàöåì äàåò íàì òî, ÷òî âñå ïðèíèìàåìûå ñëîâà èìåþò âèäïðèíàäëåæàò ÿçûêóan bn ,òî åñòüL.A: òàê êàê åäèíòâåííîå ïðèíèìàþùåå ñîñòîÿíèåZ0 âåðõóøêå ñòåêà, òî åñòü, òàê êàê ïðèáóêâ a, òî ïîëó÷àåì ïðèíàäëåæíîñòü ïðèíèìàåìîãîÀíàëîãè÷íóþ ñèòóàöèþ èìååì ñ àâòîìàòîìâ àâòîìàòå q2 ,â êîòîðîå ìîæíî ïîïàñòü ïðèýòîì ïåðåõîäå â ñòåêå íå ìîæåò áûòüñëîâà êL.Òàêèì îáðàçîì ìû äîêàçàëè, ÷òî äëÿ îáîèõ àâòîìàòîâ ðàñïîçíàâàåìûé ÿçûê åñòü2L.2Óïðàæíåíèå 2Äëÿ òîãî, ÷òîáû ïîêàçàòü, ÷òî äàííûé àâòîìàò ÿâëÿåòñÿ äåòåðìèíèðîâàííûì, ïåðå÷èñëèìäëÿ êàæäîé âåðøèíû âñå ðàçëè÷íûå ïàðû(σ ∈ Σ, z ∈ Γ),ïî êîòîðûì ñóùåñòâóåò îòîáðà-æåíèå, ïðè ýòîì êîëè÷åñòâî îòîáðàæåíèé äîëæíî áûòü ðàâíî êîëè÷åñòâó ðàçëè÷íûõ ïàð.Òàêæå, ïî ëþáîìó ñèìâîëó èçΓ íå ñóùåñòâóåò îòîáðàæåíèé îäíîâðåìåííî ïî ε è σ ∈ SigmaA : q0 : (a, Z0 ), (a, a), (b, a)A : q1 : (b, a), (ε, Z0 )A : q2 : ∅Äëÿ àâòîìàòàA çàìå÷àåì, ÷òî, âî-ïåðâûõ, êîëè÷åñòâî îòîáðàæåíèé ðàâíî êîëè÷åñòâó ðàç-ëè÷íûõ ïàð è, âî-âòîðûõ, äëÿ êàæäîãî ñèìâîëà ñòåêà è ñîñòîÿíèÿ àâòîìàòà íåò ïåðåõîäà ïîσ ∈ Sigmaε-ïåðåõîäàèîäíîâðåìåííî (íàïðèìåð, äëÿq1 , Z0ñóùåñòâóåòε-ïåðåõîä,îäíàêîäðóãèõ ïåðåõîäîâ íåò).B : q0 : (a, Z0 ), (a, a), (b, a)B : q1 : (b, a), (ε, Z0 )Ãäå, àíàëîãè÷íî, íåò íåîäíîçíà÷íûõ ïåðåõîäîâ.
Òî åñòü îáà àâòîìàòà ÿâëÿþòñÿ íåäåòåðìèíèðîâàííûìè.3Óïðàæíåíèå 3Ðàññìîòðèì ñëîâîw = σ1 σ2 σ̄1 σ̄2 = ([)].Ïîíÿòíî, ÷òî ñêîáî÷íûå èòîãè ïåðâîãî è âòîðîãîòèïîâ äëÿ äàííîãî ñëîâà íà ëþáîì ïðåôèêñå íå ìåíåå íóëÿ è ðàâíû íóëþ íà âñåì ñëîâå,îäíàêî äàííîå ñëîâî íå ïðèíàäëåæèò ÿçûêó ÄèêàDn . ñàìîì äåëå, íàì íóæíî ïîêàçàòü, ÷òî äàííîå ñëîâî íå âûâîäèòñÿ â ãðàììàòèêå G ÿçûêàDn .
Ïóñòü ýòî íå òàê è ñóùåñòâóåò âûâîä, òîãäà, òàê êàê ãðàììàòèêà ÿâëÿåòñÿ êîíòåêñòíîñâîáîäíîé, òî ñóùåñòâóåò ëåâûé âûâîä ýòîãî ñëîâà. Òîãäà â äàííîì âûâîäå ñóùåñòâóåò ïðîäóêöèÿ âèäàS → () èëè S → (S), òàê êàê ïåðâûé ñèìâîë êðóãëàÿ îòêðûâàþùàÿñÿ ñêîáêà.Ïåðâîãî òèïà ïðîäóêöèè íåò â âûâîäå, òàê êàê â äàííîì ñëîâå ìåæäó êðóãëûìè ñêîáêàìèåñòü êâàäðàòíàÿ. Ïóñòü êðóãëûå ñêîáêè èç íàøåãî ñëîâà ïîðîæäåíû âòîðîé ïðîäóêöèè.
Íîòîãäà ñèìâîë] ìîæíî âûâåñòè èç S , ÷òî íå âåðíî, òàê êàê ñêîáî÷íûé èòîã âòîðîãî òèïà äëÿäàííîãî ñëîâà íå ðàâåí íóëþ. Ñëåäîâàòåëüíî, äàííîå ñëîâî íå ïðèíàäëåæèò ÿçûêó Äèêà,õîòÿ äëÿ íåãî âûïîëíÿåòñÿ óïîìÿíóòîå â çàäàíèè óòâåðæäåíèå.34Çàäà÷à 1P = {{[1 , [2 , ]1 , ]2 }, {0, 1, Z0 }, {q0 , q1 }, q0 , Z0 , δ, F = ∅}[1 , Z0 /1Z0 ;[1 , 2/12;[2 , 1/21;ε, Z0 /ε[1 , 1/11[2 , Z0 /2Z0[2 , 2/22]1 , 1/εq0Ãäå äàííûé àâòîìàòP]1 , 1/εε, Z0 /ε]2 , 2/ε]2 , 2/εq1ÿâëÿåòñÿ äîïóñêàþùèì ïî ïóñòîìó ñòåêó. Äîêàæåì òî, ÷òî äàííûéÌÏ-àâòîìàò ðàñïîçíàåò ÿçûêL.Äîêàæåì äàííîå óòâåðæäåíèå ïî èíäóêöèè, ïàðàìåòð ÷åòíàÿ äëèíà ñëîâà èçL.•L äëèíû 0 è 2 áóäóò ïðèíÿòû àâòîìàòîì, òàê êàê òàêèõ ñëîâ âñåãî òðè: {[1 ]1 , [2 ]2 ε}.
Òî åñòü ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèé äëÿ ïåðâîãî ñëîâà (q0 , [1 ]1 , Z0 ) ` (q0 , ]1 , 1Z0 ) ` (q1 , ε, Z0 ) ` (q1 , ε, ε). Äëÿ âòîðîãî ñëîâà ïîñëåäîâàòåëüíîñòü àíàëîãè÷íà. Ïóñòîå ñëîâî ïðèíèìàåòñÿ òàê êàê (q0 , ε, Z0 ) ` (q0 , ε, ε).•L äëèíû 2n ïðèíèìàþòñÿ àâòîìàòîì, òîãäà äîêàæåì, ÷òî ñëîâàèç L äëèíû 2(n + 1) òàêæå ïðèíèìàþòñÿ àâòîìàòîì. Ïóñòü w ∈ L : |w| = 2(n + 1),00òîãäà w[1] = w̄[2(n + 1)], ïðè ýòîì ïîíÿòíî, ÷òî w = w[2, 2(n + 1) − 1] ∈ L, |w | =02(n + 1).
Òîãäà, òàê êàê ñëîâî w àâòîìàòîì ïðèíèìàåòñÿ, à îáðàáîòêà ýòîãî ïîäñëîâà1 èìååìíà÷èíàåòñÿ â ñîñòîÿíèè q0 ïî òåîðåìå 6.5Áàçà. Ñëîâà èçØàã. Ïóñòü ñëîâà èç(q0 , [k w0 ]k , Z0 ) ` (q0 , w0 ]k , kZ0 ) `∗ (q 0 , ]k , kZ0 ) ` (q1 , ε, Z0 ) ` (q1 , ε, ε)Òàêèì îáðàçîì, ñëîâà èçòîìàòîìPëåæàò âL.Lïðèíèìàþòñÿ àâòîìàòîìP.Äîêàæåì, ÷òî ñëîâà, ïðèíÿòûå àâ-Ïî çàäàííîé â àâòîìàòå ôóíêöèè ïåðåõîäà, ïðè ñ÷èòûâàíèè îòêðû-âàþùåéñÿ ñêîáêè ïåðâîãî òèïà â ñòåê êëàäåòñÿ åäèíèöà, à ïðè ñ÷èòûâàíèè çàêðûâàþùåéñÿñêîáêè ïåðâîãî òèïà åäèíèöà çàáèðàåòñÿ èç ñòåêà, ÷òî òàêæå ñïðàâåäëèâî äëÿ âòîðîãîòèïà è äâîéêè.
Åñëè ñëîâî ïðèíÿòî àâòîìàòîì, òî êîëè÷åñòâî îòêðûâàþùèõñÿ ñêîáîê äàííîãî òèïà ðàâíî êîëè÷åñòâó çàêðûâàþùèõñÿ, òàê êàê ïðè ïðèíÿòèè ñëîâà ñòåê ïóñò. Ýòîîçíà÷àåò, ÷òî ñêîáî÷íûé èòîã ëþáîãî òèïà ðàâåí íóëþ.Îòìåòèì òàêæå, ÷òî â ïðèíÿòîì ñëîâå ïîñëå ëþáîãî ñèìâîëà çàêðûâàþùåéñÿ ñêîáêè íåìîæåò áûòü îòêðûâàþùåéñÿ, òàê êàê â ýòîì ñëó÷àå àâòîìàò áû ñëîìàëñÿ, òàê êàê èç ñîñòîÿíèÿq1íåò îòîáðàæåíèÿ ïî îòêðûâàþùèìñÿ ñêîáêàì. Èç ýòîãî ñëåäóåò, ÷òî ïðèíÿòûåñëîâà èìåþò âèä1([1 |[2 )∗ (1 ]|2 ])∗ïðè÷åì êîëè÷åñòâî îòêðûâàþùèõñÿ ñêîáîê íåêîòîðîãî òèïàÕîïêðîôò, Ìîòâàíè, Óëüìàí - Ââåäåíèå â òåîðèþ àâòîìàòîâ, ÿçûêîâ è âû÷èñëåíèé4ðàâíî êîëè÷åñòâó çàêðûâàþùèõñÿ ñêîáîê ýòîãî òèïà (èç ïðåäûäóùåãî àáçàöà).
Ñëåäîâàòåëüíî, ïðèíÿòîå ñëîâî èìååò ÷åòíóþ äëèíó.w ∈ ([1 |[2 )∗ (1 ]|2 ])∗Ïóñòüïðèíÿòî ñòåêîì,|w| = 2n,òîãäà∀i 6 n, w[i] = w̄[2n − i + 1],òàêêàê ïîäñëîâî ìåæäó ýòèìè ñèìâîëàìè ñîäåðæèò îäèíàêîâîå êîëè÷åñòâî îòêðûâàþùèõñÿ èçàêðûâàþùèõñÿ ñêîáîê, òî åñòü ïðè åãî îáðàáîòêå ñòåê âåðíåòñÿ ê ñîñòîÿíèþ, â êîòîðîì îííàõîäèëñÿ ïîñëå îáðàáîòêèw[i]. Òîãäà ïðè îáðàáîòêå w[wn−i+1] àâòîìàò íå ëîìàåòñÿ ëèøüâ òîì ñëó÷àå, åñëè òèï ýòîé çàêðûâàþùåéñÿ ñêîáêè òàêîé æå, êàê è òèï îòêðûâàþùåéñÿñêîáêèw[i].w ∈ L, òàê êàê w[n, n + 1] ∈ L ⇒ w[n − 1, n + 2] ⇒ .
. . ⇒ w[1, 2n] ∈ L,w[n, n+1] - âûâîäèòñÿ èç ãðàììàòèêè ïî êîìïîçèöèè S → σi σ̄i , à êàæäîå ñëåäóþùååïîñëå äâîéíîé ñòðåëêè âûâîäèòñÿ ïî êîìïîçèöèè S → σi S σ̄i , ãäå S ðàñêðûâàåòñÿ âÈç ýòîãî ïîëó÷àåì, ÷òîòàê êàêñëîâîïðåäûäóùåå äâîéíîé ñòðåëêå ñëîâî.w ∈ ([1 |[2 )∗ (1 ]|2 ])∗w ∈ L.Òî åñòüÒåïåðü íåìíîãî òðàíñôîðìèðóåì àâòîìàò, ÷òîáû îí ïðèíèìàë èòåðàöèþ, äîáàâèâε, Z0 /Z0Òàêèì îáðàçîì ìû ïîëó÷èëè, ÷òîàâòîìàò ðàñïîçíàåò ÿçûêïåðåõîä èçq1âq0èw ∈ D2 ,òî åñòüL.Íàçîâåì åãî[1 , Z0 /1Z0 ;[1 , 2/12;[2 , 1/21;ε, Z0 /εP 0.[1 , 1/11[2 , Z0 /2Z0[2 , 2/22]1 , 1/ε]1 , 1/ε]2 , 2/ε]2 , 2/εq0q1ε, Z0 /Z0Î÷åâèäíî, ÷òî âñå ñëîâà èçíîå ïîäñëîâî èçâq0L∗ïðèíèìàþòñÿ ýòèì àâòîìàòîì, òàê êàê, îáðàáàòûâàÿ î÷åðåä-L, àâòîìàò áóäåò íàõîäèòüñÿ â q1ñZ0â ñòåêå.
Ïåðåéäÿ ïî íîâîìó ïåðåõîäóàòîìàò îáðàáîòàåò ñëåäóþùåå ïîäñëîâî èëè çàâåðøèò îáðàáîòêó, î÷èñòèâ ñòåê îòZ0 .∗∗Òàêæå, ëþáîå ñëîâî íå èç L íå áóäåò ïðèíèìàòüñÿ àâòîìàòîì. Ïóñòü w 6∈ L ïðèíèìàåòñÿpp 0 ss∗àâòîìàòîì, òîãäà îíî ïðåäñòàâèìî â âèäå w = wL w wL , wl , wL ∈ L , ãäå ëþáîé ïðåôèêñ èp0ëþáîé ñóôôèêñ w íå ëåæèò â L. Ïðè îáðàáîòêå wL àâòîìàò áóäåò íàõîäèòüñÿ â ñîñòîÿíèèq0 ñî ñòåêîì Z0 , òàê êàê ñòåê ïîñëå îáðàáîòêè ñóôôèêñà èç L ïóñò, òî åñòü äëÿ îáðàáîòêèñëåäóþùèõ ñèìâîëîâ íóæíî íàõîäèòüñÿ â ñîñòîÿíèèÏîñëå îáðàáîòêè ïîäñëîâàw0àâòîìàò áóäåò èìåòü ïóñòîé ñòåê, òàê êàê â ïðîòèâíîì ñëó-÷àå îñòàâøàÿñÿ ïîñëåäîâàòåëüíîñòü ïîäñëîâ èçïîñëå îáðàáîòêè, è â ñîñòîÿíèèïîäñëîâà èçLq0 .q0 ,Láóäåò èìåòü íåïóñòîé ñòåê (ñ 1 èëè 0)òàê êàê î÷èñòêà ñòåêà îòZ0èëè îáðàáîòêà ñëåäóþùåãîìîæåò íà÷èíàòüñÿ ëèøü îòòóäà.âûïèøåì ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèé, îáðàáàòûâàþùóþ ñëîâî5w:p 0 sss(q0 , wLw wL , Z0 ) `∗ (q0 , w0 wL, Z0 ) `∗ (q0 , wL, Z0 ) `∗ (q0 , ε, Z0 ) ` (q0 , ε, ε)Îáðàòèì âíèìàíèå íà êóñîêss(q0 , w0 wL, Z0 ) `∗ (q0 , wL, Z0 )×òî îçíà÷àåò, ÷òî ñëîâîw0áûëî áû ïðèíÿòî àâòîìàòîì êàê(q0 , w0 , Z0 ) `∗ (q1 , ε, Z0 ) ` (q0 , ε, Z0 ) ` (q0 , ε, ε)Îáðàòèì âíèìàíèå íà ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèé, çà èñêëþ÷åíèåì ïîñëåäíèõ äâóõ.Åñëè áû ìû ïîäàëèw0àâòîìàòóPíà âõîä, òî â àâòîìàòåPñóùåñòâóåò ïîñëåäîâàòåëüíîñòüîòîáðàæåíèé ñ ýòîé æå ïîñëåäîâàòåëüíîñòüþ êîôèãóðàöèé.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
