В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 13
Текст из файла (страница 13)
Ýòèîïðåäåëåíèÿ ýêâèâàëåíòíû, èáî ñïðàâåäëèâàÒåîðåìà 4.1. ßçûê äîïóñêàåòñÿ ÌÏ-àâòîìàòîì òîãäà è òîëüêî òîãäà, êîãäà îí äîïóñêàåòñÿ (íåêîòîðûìäðóãèì àâòîìàòîì) îïóñòîøåíèåì ìàãàçèíà.84Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçÄîêàçàòåëüñòâî. Ïóñòü L = L(M ) äëÿ íåêîòîðîãî ÌÏàâòîìàòà M = (Q, T, Γ, D, q0 , Z0 , F ). Ïîñòðîèì íîâûé ÌÏàâòîìàò M 0 , äîïóñêàþùèé òîò æå ÿçûê îïóñòîøåíèåì ìàãàçèíà.Ïóñòü M 0 = (Q ∪ {q00 , qe }, T, Γ ∪ {Z00 }, D0 , q00 , Z00 , ∅), ãäåôóíêöèÿ ïåðåõîäîâ D0 îïðåäåëåíà ñëåäóþùèì îáðàçîì:1. Åñëè (r, u) ∈ D(q, a, Z), òî (r, u) ∈ D0 (q, a, Z) äëÿ âñåõq ∈ Q, a ∈ T ∪ {e} è Z ∈ Γ (ìîäåëèðîâàíèå Ì);2.
D0 (q00 , e, Z00 ) = {(q0 , Z0 Z00 )} (íà÷àëî ðàáîòû);3. Äëÿ âñåõ q ∈ F è Z ∈ Γ ∪ {Z00 } ìíîæåñòâî D0 (q, e, Z)ñîäåðæèò (qe , e) (ïåðåõîä â ñîñòîÿíèå ñîêðàùåíèÿ ìàãàçèíà áåç ïðîäâèæåíèÿ);4. D0 (qe , e, Z) = {(qe , e)} äëÿ âñåõ Z ∈ Γ ∪ {Z00 };(ñîêðàùåíèå ìàãàçèíà).Àâòîìàòñíà÷àëàïåðåõîäèòâêîíôèãóðàöèþ(q0 , w, Z0 Z00 ) ñîîòâåòñòâåííî îïðåäåëåíèþ D0 â ï.2, çàòåì â (q, e, Y1 .
. .Yk Z00 ), q ∈ F ñîîòâåòñòâåííî ï.1, çàòåì â(qe , e, Y1 . . .Yk Z00 ), q ∈F ñîîòâåòñòâåííî ï.3, çàòåì â (qe , e, e)ñîîòâåòñòâåííî ï.4. Íåòðóäíî ïîêàçàòü ïî èíäóêöèè, ÷òî(q0 , w, Z0 ) `+ (q, e, u) (ãäå q ∈ F ) âûïîëíÿåòñÿ äëÿ àâòîìàòà M òîãäà è òîëüêî òîãäà, êîãäà (q00 , w, Z00 ) `+ (qe , e, e)âûïîëíÿåòñÿ äëÿ àâòîìàòà M 0 . Ïîýòîìó L(M ) = L0 , ãäåL0 ÿçûê, äîïóñêàåìûé àâòîìàòîì M 0 îïóñòîøåíèåììàãàçèíà.Îáðàòíî, ïóñòü M = (Q, T, Γ, D, q0 , Z0 , ∅) ÌÏàâòîìàò, äîïóñêàþùèé îïóñòîøåíèåì ìàãàçèíà ÿçûê L.
Ïîñòðîèì àâòîìàò M 0 , äîïóñêàþùèé òîò æå ÿçûê ïî çàêëþ÷èòåëüíîìó ñîñòîÿíèþ.Ïóñòü M 0 = (Q ∪ {q00 , qf }, T, Γ ∪ {Z00 }, D0 , q00 , Z00 , {qf }),ãäå D0 îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:1. D0 (q00 , e, Z00 ) = {(q0 , Z0 Z00 )} ïåðåõîä â ¾ðåæèì M ¿;2. Äëÿ êàæäîãî q ∈ Q, a ∈ T ∪ {e}, è Z ∈ Γ îïðåäåëèìD0 (q, a, Z) = D(q, a, Z) ðàáîòà â ¾ðåæèìå M ¿;3. Äëÿ âñåõ q ∈ Q, (qf , e) ∈ D0 (q, e, Z00 ) ïåðåõîä â çàêëþ÷èòåëüíîå ñîñòîÿíèå.4.1. ÊÑ-ãðàììàòèêè è ÌÏ-àâòîìàòû85Íåòðóäíî ïîêàçàòü ïî èíäóêöèè, ÷òî L = L(M 0 ).Îäíèì èç âàæíåéøèõ ðåçóëüòàòîâ òåîðèè êîíòåêñòíîñâîáîäíûõ ÿçûêîâ ÿâëÿåòñÿ äîêàçàòåëüñòâî ýêâèâàëåíòíîñòè ÌÏ-àâòîìàòîâ è ÊÑ-ãðàììàòèê.Òåîðåìà 4.2. ßçûê ÿâëÿåòñÿ êîíòåêñòíî-ñâîáîäíûìòîãäà è òîëüêî òîãäà, êîãäà îí äîïóñêàåòñÿ ÌÏ-àâòîìàòîì.Äîêàçàòåëüñòâî.
Ïóñòü G=(N, T, P, S) ÊÑ-ãðàììàòèêà. Ïîñòðîèì ÌÏ-àâòîìàò, äîïóñêàþùèé ÿçûê L(G) îïóñòîøåíèåì ìàãàçèíà.Ïóñòü M = ({q}, T, N ∪T, D, q, S, ∅), ãäå D îïðåäåëÿåòñÿñëåäóþùèì îáðàçîì:1. Åñëè A → u ∈ P , òî (q, u) ∈ D(q, e, A);2. D(q, a, a) = {(q, e)} äëÿ âñåõ a ∈ T .Ôàêòè÷åñêè, ýòîò ÌÏ-àâòîìàò â òî÷íîñòè ìîäåëèðóåòâñå âîçìîæíûå âûâîäû â ãðàììàòèêå G. Íåòðóäíî ïîêàçàòüïî èíäóêöèè, ÷òî äëÿ ëþáîé öåïî÷êè w ∈ T ∗ âûâîä S ⇒+ wâ ãðàììàòèêå G ñóùåñòâóåò òîãäà è òîëüêî òîãäà, êîãäàñóùåñòâóåò ïîñëåäîâàòåëüíîñòü òàêòîâ (q, w, S) `+ (q, e, e)àâòîìàòà M .Íàîáîðîò, ïóñòü äàí M = (Q, T, Γ, D, q0 , Z0 , ∅) ÌÏàâòîìàò, äîïóñêàþùèé îïóñòîøåíèåì ìàãàçèíà ÿçûê L.Ïîñòðîèì ãðàììàòèêó G, ïîðîæäàþùóþ ÿçûê L.Ïóñòü G = ({ [qZr] | q, r ∈ Q, Z ∈ Γ} ∪ {S}, T, P, S), ãäåP ñîñòîèò èç ïðàâèë ñëåäóþùåãî âèäà:1.
S → [q0 Z0 q] ∈ P äëÿ âñåõ q ∈ Q.2. Åñëè (r, e) ∈ D(q, a, Z), òî [qZr] → a ∈ P , a ∈ T ∪ {e};3. Åñëè (r, X1 . . . Xk ) ∈ D(q, a, Z), k > 1, òî[qZsk ] → a[rX1 s1 ][s1 X2 s2 ] . . . [sk−1 Xk sk ]äëÿ ëþáîãî íàáîðà s1 , s2 , . . . , sk ñîñòîÿíèé èç Q;86Ãëàâà 4.
Ñèíòàêñè÷åñêèé àíàëèçÍåòåðìèíàëû è ïðàâèëà âûâîäà ãðàììàòèêè îïðåäåëåíû òàê, ÷òî ðàáîòå àâòîìàòà M ïðè îáðàáîòêå öåïî÷êè wñîîòâåòñòâóåò ëåâîñòîðîííèé âûâîä w â ãðàììàòèêå G.Èíäóêöèåé ïî ÷èñëó øàãîâ âûâîäà â G èëè ÷èñëó òàêòîâ M íåòðóäíî ïîêàçàòü, ÷òî (q, w, A) `+ (p, e, e) òîãäà èòîëüêî òîãäà, êîãäà [qAp] ⇒+ w.Òîãäà, åñëè w ∈ L(G), òî S ⇒ [q0 Z0 q] ⇒+ w äëÿ íåêîòîðîãî q ∈ Q. Ñëåäîâàòåëüíî, (q0 , w, Z0 ) `+ (q, e, e) è ïîýòîìów ∈ L. Àíàëîãè÷íî, åñëè w ∈ L, òî (q0 , w, Z0 ) `+ (q, e, e).Çíà÷èò, S ⇒ [q0 Z0 q] ⇒+ w, è ïîýòîìó w ∈ L(G).ÌÏ-àâòîìàò M = (Q, T, Γ, D, q0 , Z0 , F ) íàçûâàåòñÿ äåòåðìèíèðîâàííûì (ÄÌÏ-àâòîìàòîì), åñëè âûïîëíåíû äâàñëåäóþùèõ óñëîâèÿ:(1) Ìíîæåñòâî D(q, a, Z) ñîäåðæèò íå áîëåå îäíîãî ýëåìåíòà äëÿ ëþáûõ q ∈ Q, a ∈ T ∪ {e}, Z ∈ Γ;(2) Åñëè D(q, e, Z) 6= ∅, òî D(q, a, Z) = ∅ äëÿ âñåõ a ∈ T .Äîïóñêàåìûé ÄÌÏ-àâòîìàòîì ÿçûê íàçûâàåòñÿ äåòåðìèíèðîâàííûì ÊÑ-ÿçûêîì.Òàê êàê ôóíêöèÿ ïåðåõîäîâ ÄÌÏ-àâòîìàòà ñîäåðæèòíå áîëåå îäíîãî ýëåìåíòà äëÿ ëþáîé òðîéêè àðãóìåíòîâ,ìû áóäåì ïîëüçîâàòüñÿ çàïèñüþ D(q, a, Z) = (p, u) äëÿ îáîçíà÷åíèÿ D(q, a, Z) = {(p, u)}.Ïðèìåð 4.2.
Ðàññìîòðèì ÄÌÏ-àâòîìàòM = ({q0 , q1 , q2 }, {a, b, c}, {Z, a, b}, D, q0 , Z, {q2 }),ôóíêöèÿ ïåðåõîäîâ êîòîðîãî îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:D(q0 , X, Y ) = (q0 , XY ), X ∈ {a, b}, Y ∈ {Z, a, b},D(q0 , c, Y ) = (q1 , Y ), Y ∈ {a, b},D(q1 , X, X) = (q1 , e), X ∈ {a, b},D(q1 , e, Z) = (q2 , e).Íåòðóäíî ïîêàçàòü, ÷òî ýòîò äåòåðìèíèðîâàííûé ÌÏ-àâòîìàò äîïóñêàåò ÿçûê L = {wcwR |w ∈ {a, b}+ }.4.1. ÊÑ-ãðàììàòèêè è ÌÏ-àâòîìàòû87Ê ñîæàëåíèþ, ÄÌÏ-àâòîìàòû èìåþò ìåíüøóþ ðàñïîçíàâàòåëüíóþ ñïîñîáíîñòü, ÷åì ÌÏ-àâòîìàòû. Äîêàçàíî, â÷àñòíîñòè, ÷òî ñóùåñòâóþò ÊÑ-ÿçûêè, íå ÿâëÿþùèåñÿ äåòåðìèíèðîâàííûìè ÊÑ-ÿçûêàìè (òàêîâûì, íàïðèìåð, ÿâëÿåòñÿ ÿçûê èç ïðèìåðà 4.1).Ðàññìîòðèì åù¼ îäèí âàæíûé âèä ÌÏ-àâòîìàòà.Ðàñøèðåííûì àâòîìàòîì ñ ìàãàçèííîé ïàìÿòüþ íàçîâ¼ì ñåì¼ðêó M = (Q, T, Γ, D, q0 , Z0 , F ), ãäå ñìûñë âñåõ ñèìâîëîâ òîò æå, ÷òî è äëÿ îáû÷íîãî ÌÏ-àâòîìàòà, êðîìå D,ïðåäñòàâëÿþùåãî ñîáîé îòîáðàæåíèå êîíå÷íîãî ïîäìíîæåñòâà ìíîæåñòâà Q × (T ∪ {e}) × Γ∗ âî ìíîæåñòâî êîíå÷íûõïîäìíîæåñòâ ìíîæåñòâà Q × Γ∗ .
Âñå îñòàëüíûå îïðåäåëåíèÿ (êîíôèãóðàöèè, òàêòà, äîïóñòèìîñòè) äëÿ ðàñøèðåííîãî ÌÏ-àâòîìàòà îñòàþòñÿ òàêèìè æå, êàê äëÿ îáû÷íîãî.Òåîðåìà 4.3. Ïóñòü M = (Q, T, Γ, D, q0 , Z0 , F ) ðàñøèðåííûé ÌÏ-àâòîìàò. Òîãäà ñóùåñòâóåò ÌÏ-àâòîìàò M 0 , òàêîé, ÷òî L(M 0 ) = L(M ).Ðàñøèðåííûé ÌÏ-àâòîìàò M = (Q, T, Γ, D, q0 , Z0 , F )íàçûâàåòñÿ äåòåðìèíèðîâàííûì, åñëè âûïîëíåíû ñëåäóþùèå óñëîâèÿ:(1) Ìíîæåñòâî D(q, a, u) ñîäåðæèò íå áîëåå îäíîãî ýëåìåíòà äëÿ ëþáûõ q ∈ Q, a ∈ T ∪ {e}, u ∈ Γ∗ ;(2) Åñëè D(q, a, u) 6= ∅, D(q, a, v) 6= ∅ è u 6= v , òî íåñóùåñòâóåò öåïî÷êè x òàêîé, ÷òî u = vx èëè v = ux;(3) Åñëè D(q, a, u) 6= ∅, D(q, e, v) 6= ∅, òî íå ñóùåñòâóåòöåïî÷êè x òàêîé, ÷òî u = vx èëè v = ux.Òåîðåìà 4.4.
Ïóñòü M = (Q, T, Γ, D, q0 , Z0 , F ) ðàñøèðåííûé ÄÌÏ-àâòîìàò. Òîãäà ñóùåñòâóåò ÄÌÏ-àâòîìàò M 0 , òàêîé, ÷òî L(M 0 ) = L(M ).ÄÌÏ-àâòîìàò è ðàñøèðåííûé ÄÌÏ-àâòîìàò ëåæàò âîñíîâå ðàññìàòðèâàåìûõ äàëåå â ýòîé ãëàâå, ñîîòâåòñòâåííî, LL- è LR-àíàëèçàòîðîâ.88Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçÎïðåäåëåíèå. Ãîâîðÿò, ÷òî ÊÑ-ãðàììàòèêà íàõîäèòñÿ âíîðìàëüíîé ôîðìå Õîìñêîãî, åñëè êàæäîå ïðàâèëî èìååò âèä:(1) ëèáî A → BC, A, B, C - íåòåðìèíàëû;(2) ëèáî A → a, a - òåðìèíàë;(3) ëèáî S → e è â ýòîì ñëó÷àå S - íå âñòðå÷àåòñÿ âïðàâûõ ÷àñòÿõ ïðàâèë.Óòâåðæäåíèå. Ëþáóþ ÊÑ-ãðàììàòèêó ìîæíî ïðåîáðàçîâàòü â ýêâèâàëåíòíóþ åé â íîðìàëüíîé ôîðìå Õîìñêîãî.Óòâåðæäåíèå. Åñëè ÊÑ-ãðàììàòèêà íàõîäèòñÿ â íîðìàëüíîé ôîðìå Õîìñêîãî, òîãäà äëÿ ëþáîé öåïî÷êè α,åñëè α ∈ L(G) è m âûñîòà äåðåâà âûâîäà ñ êðîíîé α,|α| 6 2m−1 .Òåîðåìà 4.5.
(Ëåììà î ðàçðàñòàíèè äëÿ êîíòåêñòíîñâîáîäíûõ ÿçûêîâ). Äëÿ ëþáîãî ÊÑ-ÿçûêà L ñóùåñòâóþò òàêèå öåëûå l è k , ÷òî ëþáàÿ öåïî÷êà α ∈ L, |α| > l,ïðåäñòàâèìà â âèäå α = uvwxy , ãäå(1) |vwx| 6 k(2) vx 6= e(3) uv i wxi y ∈ L äëÿ ëþáîãî i > 0.Äîêàçàòåëüñòâî.Ïóñòü L = L(G), ãäå G = (N, Σ, P, S) - êîíòåêñòíîñâîáîäíàÿ ãðàììàòèêà â íîðìàëüíîé ôîðìå Õîìñêîãî. Îáîçíà÷èì ÷åðåç n ÷èñëî íåòåðìèíàëîâ, ò.å. n = |N |, è ðàññìîòðèì l = 2n è k = 2n+1 .Äëÿ äîêàçàòåëüñòâà òîãî, ÷òî l è k óäîâëåòâîðÿþò óñëîâèþ òåîðåìû, ðàññìîòðèì ïðîèçâîëüíóþ öåïî÷êó α ∈ L,äëÿ êîòîðîé |α| > l = 2n .  ñèëó Óòâåðæäåíèÿ ïîëó÷àåì,÷òî âûñîòà äåðåâà ñ êðîíîé α áîëüøå n + 1 è åñòü ïóòü ïîäåðåâó (îáîçíà÷èì åãî ÷åðåç P ), êîòîðûé ïðîõîäèò áîëåå÷åì ÷åðåç n + 1 âåðøèí.
Îòñþäà ïî îïðåäåëåíèþ äåðåâàâûâîäà èìååì, ÷òî P ñîäåðæèò áîëåå n âåðøèí, ïîìå÷åííûõ íåòåðìèíàëàìè. Òàêèì îáðàçîì, ñóùåñòâóåò íåòåðìèíàë, êîòîðûé ìåòèò íå ìåíåå äâóõ âåðøèí ïóòè P . Ñðåäè4.2. Ïðåîáðàçîâàíèÿ ÊÑ-ãðàììàòèê89âñåõ òàêèõ íåòåðìèíàëîâ ïóñòü A òàêîé, ÷òî åãî âõîæäåíèå, áëèæàéøåå ê ëèñòó, íå ñîäåðæèò äðóãèõ íåòåðìèíàëîâ,îáëàäàþùèõ ýòèì ñâîéñòâîì (åñëè áû ýòî áûëî íå òàê, òîâûáðàëè áû ýòîò äðóãîé). Ïóñòü q âõîæäåíèå A, áëèæàéøåå ê ëèñòó, p ðàñïîëîæåííîå âûøå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
