7 неделя (1178960), страница 2
Текст из файла (страница 2)
Âî âòîðîì ñëó÷àå, ñ÷èòàåì âñå áóêâûîñòàâàÿñü â ñîñòîÿíèèèç ñòåêà ñ÷èòàííóþ áóêâóc,è ïðî÷èòàåì ñëîâîq0 , çàòåì ïåðåéäåì â q1 ,ω1R , âûáðàñûâàÿ èç ñòåêàω1óäàëèâñ÷èòû-âàåìûå áóêâû.  ðåçóëüòàòå ðàáîòû àâòîìàòà ñòåê îêàæåòñÿ ïóñòûì è ñëîâîωïðèìåòñÿ.• L(P ) ⊆ LÀâòîìàò ìîæåò ïðèíÿòü ñëîâî ïî ïóñòîìó ñòåêó òîëüêî â ñîñòîÿíèè q1 , êóäà íàäîïîïàñòü èç q0 .  q1 ìîæíî òîëüêî èçâëåêàòü áóêâû èç ñòåêà, âñå áóêâû äîáàâëÿþòñÿ â ñîñòîÿíèèq0 .Àâòîìàò ñìîæåò ïðèíÿòü ñëîâî ïî ïóñòîìó ñòåêó òîãäà èòîëüêî òîãäà, êîãäà ñ÷èòàåò â ñîñòîÿíèè q1 è âûáðîñèò èç ñòåêà òå æå áóêâû, ÷òî èñ÷èòàëèñü â ñîñòîÿíèè q0 , è êîòîðûå òåïåðü ëåæàò â ñòåêå.
Ïîñëåäíÿÿ ñ÷èòàííàÿ âñîñòîÿíèè q0 áóêâà, âîçìîæíî, áûëà âûáðîøåíà, ïåðåõîäÿ â ñîñòîÿíèå q1 áåç ñ÷èòûâàíèÿ òàêîé æå áóêâû â ñëîâå. Òàêèì îáðàçîì, âñå ïðèíÿòûå àâòîìàòîì ñëîâàèìåþò âèäω = ω1 cω1R ,ãäåc- îäíà èç áóêâ àëôàâèòà, ëèáîε⇒ω- ïàëèíäðîìÇàäà÷à 4: Ïîñòðîèòü ÊÑ-ãðàììàòèêó G, ïîðîæäàþùóþ L èëè ÌÏ-àâòîìàòM , ðàñïîçíàþùèé L. L = {ai bj ck | i = j ∨ i = k; i, j, k ≥ 0}Àâòîìàòb, a/ε | ε, Z0 /εq1M:c, Z0 /Z0 | ε, Z0 /εc, Z0 /Z0q2a, Z0 /aZ0 | a, a/aab, a/εc, Z0 /Z0 | ε, Z0 /Z0q0c, a/εb, a/a | b, Z0 /Z0q3c, a/εb, a/a | b, Z0 /Z0 | ε, Z0 /εq4c, a/ε | ε, Z0 /εÄîêàçàòåëüñòâî.• L ⊆ L(M )Ñëîâî ω ∈ L1.ìîæåò èìåòü äâà âèäà:ω = ai bi ckÒîãäà, åñëèi > 0,ñ÷èòàåì âñåaâ ñîñòîÿíèèñèìâîëû â ñòåê. Çàòåì, ïðè ñ÷èòûâàíèèbq0 ,ïîëîæèâ âñå ñ÷èòàííûåïåðåéäåì â ñîñòîÿíèåq1è ïðèêàæäîé ñ÷èòàííîé b áóäåì óáèðàòü îäèí ñèìâîë a èç ñòåêà.
Ïîñëå ñ÷èòûâàíèÿâñåõb,êîòîðûõ ñòîëüêî æå, ñêîëüêî è áûëîa,â ñòåêå îêàæåòñÿ òîëüêîZ0 .Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÅñëè k= 0, òî î÷èñòèì ñòåê è îò Z0 , òîãäà àâòîìàò ïðèìåò ñëîâî ω ïî ïóñòîìók > 0, òî ïåðåõîäèì â ñîñòîÿíèå q2 , ñ÷èòûâàåì âñå c, íå èçìåíÿÿñòåê, à çàòåì î÷èùàåì ñòåê îò Z0 . Àâòîìàò ïðèíÿë ñëîâî ω ïî ïóñòîìó ñòåêó.Åñëè i = 0, ò.å ïåðåä íàìè ω ∈ c∗ , òî ïåðåéäåì â ñîñòîÿíèå q2 (òàê êàê ñòåêïóñò) ïî ñèìâîëó c èëè ε, â ñëó÷àå k > 0 ñ÷èòàåì âñå c, è óäàëèì èç ñòåêà Z0 .ω ïðèíÿòî àâòîìàòîì ïî ïóñòîìó ñòåêó.ñòåêó. Åñëè2.ω = ai bk ciÏðè i > 0,ñ÷èòàåì âñåâ ñòåê. Åñëèk > 0,aâ ñîñòîÿíèèq0 ,ïîëîæèâ âñå ñ÷èòàííûå ñèìâîëûòî ïåðåéäåì â ñîñòîÿíèåq3 ,ñ÷èòàåì âñåb,íå èçìåíÿÿñîäåðæèìîå ñòåêà, à çàòåì ïðèñòóïèì ê ñ÷èòûâàíèþ áóêâ c, óáèðàÿ ïî îäíîìóq4 .
 êîíöå ñ÷èòûâàíèÿ c, ñòåê áóäåòZ0 , êîòîðûé ìû óáåðåì. Àâòîìàò ïðèìåò ñëîâî ω ïî ïóñòîìóñòåêó. Åñëè k = 0, òî ñðàçó ïðèñòóïèì ê ñ÷èòûâàíèþ c, óáèðàÿ ïî îäíîìóa èç ñòåêà, è îêàæåìñÿ â ñîñòîÿíèè q4 .  êîíöå ñ÷èòûâàíèÿ c, ñòåê áóäåòñîäåðæàòü ëèøü Z0 , êîòîðûé ìû óáåðåì. Àâòîìàò ïðèìåò ñëîâî ω ïî ïóñòîìóaèç ñòåêà, è îêàæåìñÿ â ñîñòîÿíèèñîäåðæàòü ëèøüñòåêó.Åñëèi = 0,òî áóäåì ñ÷èòàòük > 0(ñëó÷àéóæå áûë ðàçîáðàíi = k = 0âûøå). Òîãäà ñ ïóñòûì ñòåêîì ìû ïåðåéäåì â ñîñòîÿíèåóáåðåì èç ñòåêàZ0 .Àâòîìàò ïðèìåò ñëîâîωq3 ,ñ÷èòàåì âñåb,ïî ïóñòîìó ñòåêó.• L(M ) ⊆ L1. Ïóñòüq1 .q0 ïåðåõîäîì ïî b, óáðàâ èç ñòåêàîäíó a.
Ñèìâîëû a ñ÷èòûâàþòñÿ òîëüêî â q0 , âñå îíè êëàäóòñÿ â ñòåê. À â q1ñ÷èòûâàþòñÿ b è óáèðàþòñÿ ñîîòâåòñòâóþùèå a. Åñëè ñòåê îêàçàëñÿ ïóñòûì,ýòî çíà÷èò, ÷òî ω = an bn = an bn c0 ∈ L2. Ïóñòüáûëî ïðèíÿòî ïî ïóñòîìó ñòåêó âωÒîãäà âq1ωàâòîìàò ìîã ïîïàñòü òîëüêî èçáûëî ïðèíÿòî ïî ïóñòîìó ñòåêó â ñîñòîÿíèèñ÷èòûâàþòñÿq2c,q2 .ñîäåðæèìîå ñòåêà íå èçìåíÿåòñÿ. Åñëè âàâòîìàò ïîïàë èç q0 , çíà÷èò ñòåê ïóñò, à çíà÷èò ñèìâîëîâÒàêæå íå áûëî ñ÷èòàíî è b. Çíà÷èò, ω = c∗ = a0 b0 cn ∈ìàò ïîïàë èçq1ïî ïóñòîìó ñòåêó (òîëüêîýòî îçíà÷àåò, ÷òîñîñòîÿíèè3.
Ïóñòüωq2q1ïîëó÷èìq3äà î÷èñòèòü ñòåê îêîí÷àòåëüíî îòωZ0q4Z0 .câq3 .q4 .îêàçûâàåòñÿ àâòîìàò, ñ÷èòûâàÿ c, ïðè÷åì óäàëÿÿ èç ñòåêàÏðèíÿòü ñëîâî âîäíîïðèïèñûâàÿ ê íåìóè ïðèíÿòü ñëîâî. Çíà÷èò â q3 ìû ïîïàëèa. Áóêâ c ìû òàêæå íå ñ÷èòàëè. Çíà÷èòáûëî ïðèíÿòî ïî ïóñòîìó ñòåêó â ñîñòîÿíèèan bn ,ìû ìîæåì ëèøü ñ÷èòûâàòü b, íå èçìåíÿÿ ñîäåðæèìîå ñòåêà,èç q1 ñ ïóñòûì ñòåêîì, ò.å â ñëîâå íåòω = b∗ = a0 bk c0 ∈ L.4. Ïóñòüâ íåì), òî ìû óæå çíàåì, ÷òîω = an bn ck ∈ Láûëî ïðèíÿòî ïî ïóñòîìó ñòåêó â ñîñòîÿíèèZ0ïåðåäàë íàì ñëîâî âèäàq2a íå áûëî ñ÷èòàíî.L. Åñëè â q2 àâòî-q4a.àâòîìàò ìîæåò òîëüêî êîãäà â ñòåêå îêàæåòñÿ òîëüêîÊðîìå ïðèíÿòèÿ ñëîâî â ñîñòîÿíèèq4 ìîãóò òîëüêî ñ÷èòûâàòüñÿ c,a.
a ñ÷èòûâàþòñÿ òîëüêî â q0 , ïðè÷åìíà êàæäûé ñ÷èòàííûé a â ñòåê êëàäåòñÿ a. Òàêèì îáðàçîì, â q4 ñòåê îïóñòååòòîãäà è òîëüêî òîãäà, êîãäà ñ÷èòàåòñÿ ñòîëüêî æå c, ñêîëüêî è a. Òîãäà ωèìååò âèä an bk cn , n > 0, ω ∈ L.ïðè÷åì óìåíüøàÿ ñîäåðæèìîå ñòåêà íàÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÇàäà÷à 5:Ïðèâåñòè àëãîðèòì ïîñòðîåíèÿ ÌÏ-àâòîìàòà P , äîïóñêàþùåãî ïîçàêëþ÷èòåëüíîìó ñîñòîÿíèþ ïî ÌÏ-àâòîìàòó N , äîïóñêàþùåãî ïî ïóñòîìó ñòåêó.Ïðèâåñòè àëãîðèòì îáðàòíîãî ïîñòðîåíèÿ ïî àâòîìàòó P , àâòîìàòà N . Åñëè âçàäà÷å 1 Âû ïîñòðîèëè N -àâòîìàò, ïîñòðîéòå ïî íåìó àíàëîãè÷íûé P -àâòîìàò,åñëè âû ïîñòðîèëè P -àâòîìàò, ïîñòðîéòå ïî íåìó àíàëîãè÷íûé N -àâòîìàò.Àëãîðèòì ïîñòðîåíèÿ ÌÏ-àâòîìàòàñîñòîÿíèþ ïî ÌÏ-àâòîìàòóN,P,äîïóñêàþùåãî ïî çàêëþ÷èòåëüíîìóäîïóñêàþùåãî ïî ïóñòîìó ñòåêó:Qp = Qn ∪ {qs , qf }, ò.å äîáàâèì ê îðèãèíàëüíûì{qs , qf } ∩ Qn = ∅.
qs ìû íàçíà÷èì íà÷àëüíûì, qf qs , Fp = {qf }1. Îïðåäåëèìåùå äâà,2. ÎïðåäåëèìΓp = Γn ∪ {Z1 },ñîñòîÿíèÿì àâòîìàòàïðèíèìàþùèì: q0p=ò.å äîáàâèì ê àëôàâèòó ñòåêà åùå îäèí ñèìâîë, ðàíåååìó íå ïðèíàäëåæàùèé. Îí áóäåò âûïîëíÿòü ðîëü ¾èñòèííîãî¿ äíà ñòåêà, àäíî äëÿ âíóòðåííåãî, ýìóëèðóåìîãî àâòîìàòàZ0-N.3. Äîïîëíèì ôóíêöèþ ïåðåõîäîâ. Âñå èìåþùèåñÿ åå çíà÷åíèÿ îñòàâèì ïðåæíèìè.Äîáàâèì åùå íåêîòîðûå ïåðåõîäû:øå íîâîå äíî(qs , ε, Z0 ) = {(q0 , Z0 Z1 )} - ïîäëîæèì ïîä Z0íà-è ïåðåéäåì â ñòàðîå íà÷àëüíîå ñîñòîÿíèå q0 . Äëÿ êàæäîãî ñîñòîÿíèÿ îðèãèíàëüíîãî àâòîìàòà, êîòîðîå ìîæåò ïðèíÿòü ïî ïóñòîìó ñòåêó (à ìîæíîZ1è äëÿ âîîáùå âñåõ ñîñòîÿíèé èçQn )îïðåäåëèì ïåðåõîä ((q, ε, Z1 )= {(qf , Z1 )}).Z0Òàêèì îáðàçîì, êîãäà ñðàáàòûâàåò ïåðåõîä, êîòîðûé ðàíüøå ñíèìàë äíî ñòåêàè ïðèíèìàë ñëîâî, åñëè âñå ñëîâî óæå ïðî÷èòàíî, ñðàçó ïîñëå ýòîãî ïðîèçîéäåòïåðåõîä âqf- ïðèíèìàþùåå ñîñòîÿíèå, ò.ê ïîäZ0ëåæèòZ1 .È ñëîâî ïðèìåòñÿ,åñëè áîëüøå áóêâ â ñëîâå íåò, èíà÷å - àâòîìàò ñëîìàåòñÿ.Èç ïîñòðîåíèÿ íîâîãî àâòîìàòà âèäíà åãî êîððåêòíîñòü.
Ò.å åñëè ðàíüøå äëÿ ëþáîãîω , ïðèíèìàåìîãî àâòîìàòîì N : (q0 , ω, Z0 ) `∗ (q, ε, ε) äëÿ íåêîòîðîãî q ∈ Q, òîòåïåðü (qs , ω, Z0 ) ` (q0 , ω, Z0 Z1 ) `∗ (q, ε, Z1 ) ` (qf , ε, Z1 ) - òîæå ïðèíèìàåòñÿ àâòîìàòîìP . À äëÿ ëþáîãî ñëîâà ω , ïðèíèìàåìîãî P , öåïî÷êà êîôèãóðàöèé îáÿçàòåëüíî èìååòâèä (qs , ω, Z0 ) ` (q0 , ω, Z0 Z1 ) `∗ (q, ε, Z1 ) ` (qf , ε, Z1 ) (ò.ê èç qs åñòü ïåðåõîä òîëüêî â q0 ,à â qf ìîæíî ïîïàñòü òîëüêî ñî ñòåêîì ñ Z1 íàâåðõó).
Íî òîãäà äëÿ ω â îðèãèíàëüíîìàâòîìàòå N öåïî÷êà êîíôèãóðàöèé èìåëà áû âèä (q0 , ω, Z0 ) `∗ (q, ε, ε), ω ïðèíèìàåòñÿàâòîìàòîì N .ñëîâàÀëãîðèòì îáðàòíîãî ïîñòðîåíèÿ ïî àâòîìàòóP,àâòîìàòàN.Qp = Qn ∪ {qs , qf }, ò.å äîáàâèì ê îðèãèíàëüíûì ñîñòîÿíèÿì àâòîìàòà{qs , qf } ∩ Qn = ∅. qs ìû íàçíà÷èì íà÷àëüíûì. Ïðèíèìàþùèõ ñîñòîÿíèéíåò (íî ïðèíèìàòüñÿ ñëîâî ïî ïóñòîìó ñòåêó áóäåò â qf ).1. Îïðåäåëèìåùå äâà,òåïåðü2. ÎïðåäåëèìΓn = Γp ∪ {Z1 },ò.å äîáàâèì ê àëôàâèòó ñòåêà åùå îäèí ñèìâîë, ðàíåååìó íå ïðèíàäëåæàùèé.
Îí áóäåò âûïîëíÿòü ðîëü ¾èñòèííîãî¿ äíà ñòåêà, àäíî äëÿ âíóòðåííåãî, ýìóëèðóåìîãî àâòîìàòàZ0-P.3. Äîïîëíèì ôóíêöèþ ïåðåõîäîâ. Âñå èìåþùèåñÿ åå çíà÷åíèÿ îñòàâèì ïðåæíèìè.Äîáàâèì åùå íåêîòîðûå ïåðåõîäû:(qs , ε, Z0 ) = {(q0 , Z0 Z1 )}- ïîäëîæèì ïîäZ0q0 . Äëÿ êàæäîãîïðèíèìàþùåãî ñîñòîÿíèÿ q ∈ F îïðåäåëèì ïåðåõîä (q, ε, α) = {(qf , α)}, ãäå α ∈ Γn .À â ñîñòîÿíèè qf áóäåì î÷èùàòü ñòåê, ò.å (qf , ε, α) = {(qf , ε, ε)}íàøå íîâîå äíîZ1è ïåðåéäåì â ñòàðîå íà÷àëüíîå ñîñòîÿíèåÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÊîððåêòíîñòü ïîëó÷åííîãî àâòîìàòà î÷åâèäíà. Ò.ê åñëèω ïðèíèìàëîñü àâòîìàòîì P ,(q0 , ω, Z0 ) `∗ (q, ε, β), ãäå q ∈ F, β - ïðîèçâîëüíî ñëîâî â àëôàâèòå Γ , òî òåïåðü äëÿ ω(qs , ω, Z0 ) ` (q0 , ω, Z0 Z1 ) `∗ (q, ε, βZ1 ) ` (qf , ε, βZ1 ) `∗ (qf , ε, ε), ò.å ω ïðèíèìàåòñÿ N ïîïóñòîìó ñòåêó.
Îáðàòíî, åñëè ω ïðèíèìàåòñÿ N ïî ïóñòîìó ñòåêó, çíà÷èò (qs , ω, Z0 ) `(q0 , ω, Z0 Z1 ) `∗ (q, ε, βZ1 ) ` (qf , ε, βZ1 ) `∗ (qf , ε, ε) (Z1 íå ìîæåò áûòü ñíÿòî íèãäå,êðîìå êàê â qf ). Íî òîãäà äëÿ P (q0 , ω, Z0 ) `∗ (q, ε, β), ãäå q ∈ F (ïî ïîñòðîåíèþ N ), àçíà÷èò ω ïðèíèìàåòñÿ è P .Äëÿ àâòîìàòà M , ïðèíèìàþùåãî ïî çàêëþ÷èòåëüíîìó ñîñòîÿíèþ, èç ïåðâîé çàäà÷èïîñòðîèì àâòîìàò P , ïðèíèìàþùèé ïî ïóñòîìó ñòåêó.ò.åa, Z0 /aZ0 | a, a/aa | a, a−1 /εqsε, Z0 /Z0 Z1q0ε, Z0 /εq1ε, Z0 /ε | ε, Z1 /ε | ε, a/ε | ε, a−1 /εε, Z0 /Z0 | ε, Z1 /Z1 | ε, a/a | ε, a−1 /a−1qfb, Z0 /a−1 Z0 | b, a/ε | b, a−1 /a−1 a−1Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ Ïðîãðàììèðîâàíèÿ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
