В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 6
Текст из файла (страница 6)
Åñëè T m îñòàíàâëèâàåòñÿ â îäíîì èç äîïóñêàþùèõ ñîñòîÿíèé, T m1 îñòàíàâëèâàåòñÿ áåç äîïóñêà. Åñëè T m îñòàíàâëèâàåòñÿ â îäíîì èç íåäîïóñêàþùèõ ñîñòîÿíèé, çíà÷èòíå äîïóñêàåò âõîä. Òîãäà T m1 äåëàåò åù¼ îäèí ïåðåõîä âñîñòîÿíèå q è äîïóñêàåò. ßñíî, ÷òî T m1 äîïóñêàåò T ∗ \ L.34Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåËåììà 2.2. Ïóñòü x1 , x2 , ...
íóìåðàöèÿ âñåõ ñëîâíåêîòîðîãî êîíå÷íîãî àëôàâèòà Σ è T1 , T2 , ... íóìåðàöèÿ âñåõ ìàøèí Òüþðèíãà ñ ëåíòî÷íûìè ñèìâîëàìè,âûáðàííûìè èç íåêîòîðîãî êîíå÷íîãî àëôàâèòà, âêëþ÷àþùåãî Σ. Ïóñòü L2 = {xi | xi äîïóñêàåòñÿ Ti }. L2- ðåêóðñèâíî ïåðå÷èñëèìîå ìíîæåñòâî, äîïîëíåíèå êîòîðîãî íå ðåêóðñèâíî ïåðå÷èñëèìî.Äîêàçàòåëüñòâî. Ñëîâà L2 äîïóñêàþòñÿ íåêîòîðîé T m,ðàáîòàþùåé ñëåäóþùèì îáðàçîì. Îòìåòèì, ÷òî T m íå îáÿçàòåëüíî îñòàíàâëèâàåòñÿ íà ñëîâàõ íå èç L2 .1.
Åñëè äàíî x, T m ïåðå÷èñëÿåò ïðåäëîæåíèÿ x1 , x2 , ...ïîêà íå íàéä¼ò xi = x, îïðåäåëÿÿ òåì ñàìûì, ÷òî x - ýòî i-åñëîâî â ïåðå÷èñëåíèè.2. T m ãåíåðèðóåò T mi è ïåðåäà¼ò óïðàâëåíèå óíèâåðñàëüíîé ìàøèíå Òüþðèíãà, êîòîðàÿ ñèìóëèðóåò T mi ñîâõîäîì x.3. Åñëè T mi îñòàíàâëèâàåòñÿ ñî âõîäîì xi è äîïóñêàåò,T m îñòàíàâëèâàåòñÿ è äîïóñêàåò; åñëè T mi îñòàíàâëèâàåòñÿ è îòâåðãàåò xi , òî T m îñòàíàâëèâàåòñÿ è îòâåðãàåò xi .Íàêîíåö, åñëè T mi íå îñòàíàâëèâàåòñÿ, òî T m íå îñòàíàâëèâàåòñÿ.4. Òàêèì îáðàçîì L2 ðåêóðñèâíî ïåðå÷èñëèìî, ïîñêîëüêó L2 - ýòî ìíîæåñòâî äîïóñêàåìîå T m.
Íî äîïîëíåíèåê L2 (∼L2 ) íå ìîæåò áûòü ðåêóðñèâíî ïåðå÷èñëèìî, ïîñêîëüêó åñëè Tj - ìàøèíà Òüþðèíãà, äîïóñêàþùàÿ ∼L2 ,òî xj ∈ ∼L2 òîãäà è òîëüêî òîãäà, êîãäà xj íå äîïóñêàåòñÿT mj . Ýòî ïðîòèâîðå÷èò óòâåðæäåíèþ, ÷òî ∼L2 - ýòî ÿçûê,äîïóñêàåìûé Tj .Òåîðåìà 2.3. Ñóùåñòâóåò ðåêóðñèâíî ïåðå÷èñëèìîåìíîæåñòâî, íå ÿâëÿþùååñÿ ðåêóðñèâíûì.Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî. Ïî ëåììå 2.2 L2 - ðåêóðñèâíî ïåðå÷èñëèìîå ìíîæåñòâî, äîïîëíåíèå êîòîðîãîíå ðåêóðñèâíî ïåðå÷èñëèìî. Åñëè áû L2 áûëî ðåêóðñèâíî,ïî ëåììå 1 ∼L2 áûëî áû ðåêóðñèâíî, è ñëåäîâàòåëüíî ðåêóðñèâíî ïåðå÷èñëèìî, ÷òî ïðîòèâîðå÷èò âòîðîé ïîëîâèíåëåììû 2.2.Ñâÿçü ìàøèí Òüþðèíãà è ãðàììàòèê òèïà 0352.5.
Ñâÿçü ìàøèí Òüþðèíãà è ãðàììàòèê òèïà 0Äîêàæåì, ÷òî ÿçûê ðàñïîçíà¼òñÿ ìàøèíîé Òüþðèíãàòîãäà è òîëüêî òîãäà, êîãäà îí ãåíåðèðóåòñÿ ãðàììàòèêîé òèïà 0. Äëÿ äîêàçàòåëüñòâà ÷àñòè ¾åñëè¿ ìû ïîñòðîèì íåäåòåðìèíèðîâàííóþ ìàøèíó Òüþðèíãà, êîòîðàÿ áóäåò íåäåòåðìèíèðîâàííî âûáèðàòü âûâîäû â ãðàììàòèêåè ñìîòðåòü, ÿâëÿåòñÿ ëè âûâîä âõîäîì.
Åñëè äà, ìàøèíàäîïóñêàåò âõîä.Äëÿ äîêàçàòåëüñòâà ÷àñòè ¾òîëüêî åñëè¿ ìû ïîñòðîèì ãðàììàòèêó, êîòîðàÿ íåäåòåðìèíèðîâàííî ãåíåðèðóåòïðåäñòàâëåíèÿ òåðìèíàëüíîé ñòðîêè è çàòåì ñèìóëèðóåòìàøèíó Òüþðèíãà íà ýòîé ñòðîêå. Åñëè ñòðîêà äîïóñêàåòñÿ íåêîòîðîé Tm, ñòðîêà êîíâåðòèðóåòñÿ â òåðìèíàëüíûåñèìâîëû, êîòîðûå îíà ïðåäñòàâëÿåò.Òåîðåìà 2.4. Åñëè L ãåíåðèðóåòñÿ ãðàììàòèêîé òèïà0, òî L ðàñïîçíà¼òñÿ ìàøèíîé Òüþðèíãà.Äîêàçàòåëüñòâî.
Ïóñòü G = (N, Σ, P, S) - ãðàììàòèêàòèïà 0 è L = L(G). Îïèøåì íåôîðìàëüíî íåäåòåðìèíèðîâàííóþ ìàøèíó Òüþðèíãà T m, äîïóñêàþùóþ L.T m = (Q, Σ, Γ, D, q0 , F )ãäå Γ = N ∪ Σ ∪ {B, #, X}.Ïðåäïîëàãàåòñÿ, ÷òî ïîñëåäíèå òðè ñèìâîëà íå âõîäÿò âN ∪ Σ.Âíà÷àëå T m ñîäåðæèò íà âõîäíîé ëåíòå w ∈ Σ∗ . T mâñòàâëÿåò # ïåðåä w, ñäâèãàÿ âñå ñèìâîëû w íà îäíó ÿ÷åéêó âïðàâî, è #S# ïîñëå w, òàê ÷òî ñîäåðæèìûì ëåíòûñòàíîâèòñÿ #w#S#.Òåïåðü T m íåäåòåðìèíèðîâàííî ñèìóëèðóåò âûâîä â G,íà÷èíàÿ ñ S . Êàæäàÿ ñåíòåíöèàëüíàÿ ôîðìà âûâîäà ïîÿâëÿåòñÿ ïî ïîðÿäêó ìåæäó ïîñëåäíèìè äâóìÿ #.
Åñëè íåêîòîðûé âûáîð ïåðåõîäîâ âåä¼ò ê òåðìèíàëüíîé ñòðîêå, îíàñðàâíèâàåòñÿ ñ w. Åñëè îíè ñîâïàäàþò, T m äîïóñêàåò.Ôîðìàëüíî, ïóñòü T m èìååò íà ëåíòå #w#A1 A2 ... Ak #.T m ïåðåäâèãàåò íåäåòåðìèíèðîâàííî ãîëîâêó ïî36Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåA1 A2 ... Ak , âûáèðàÿ ïîçèöèþ i è êîíñòàíòó r ìåæäó1 è ìàêñèìàëüíîé äëèíîé ëåâîé ÷àñòè ëþáîãî ïðàâèëà âûâîäà â P . Çàòåì T m ïðîâåðÿåò ïîäñòðîêè Ai Ai+1 ... Ai+r−1 .Åñëè Ai Ai+1 ... Ai+r−1 - ëåâàÿ ÷àñòü íåêîòîðîãî ïðàâèëàâûâîäà èç P , îíà ìîæåò áûòü çàìåíåíà íà ïðàâóþ ÷àñòü.T m ìîæåò ñäâèíóòü Ai+r Ai+r+1 ... Ak # ëèáî âëåâî, ëèáîâïðàâî, îñâîáîæäàÿ èëè çàïîëíÿÿ ìåñòî, åñëè ïðàâàÿ ÷àñòüèìååò äëèíó, îòëè÷íóþ îò r.Èç ýòîé ïðîñòîé ñèìóëÿöèè âûâîäîâ â G âèäíî, ÷òî T mïå÷àòàåò íà ëåíòå ñòðîêó âèäà #w#y#, y ∈ V ∗ â òî÷íîñòè,åñëè S ⇒G∗ y . Åñëè y = w, T m äîïóñêàåò L.Òåîðåìà 2.5.
Åñëè L ðàñïîçíà¼òñÿ íåêîòîðîé ìàøèíîé Òüþðèíãà,òî L ãåíåðèðóåòñÿ ãðàììàòèêîéòèïà 0.Äîêàçàòåëüñòâî. Ïóñòü T m = (Q, Σ, Γ, D, q0 , F ) äîïóñêàåò L. Ïîñòðîèì ãðàììàòèêó G, êîòîðàÿ íåäåðìèíèðîâàííî ãåíåðèðóåò äâå êîïèè ïðåäñòàâëåíèÿ íåêîòîðîãî ñëîâà èçΣ∗ è çàòåì ñèìóëèðóåò ïîâåäåíèå T m íà îäíîé èç êîïèé.Åñëè T m äîïóñêàåò ñëîâî, òî G òðàíñôîðìèðóåò âòîðóþêîïèþ â òåðìèíàëüíóþ ñòðîêó. Åñëè T m íå äîïóñêàåò L,òî âûâîä íèêîãäà íå ïðèâîäèò ê òåðìèíàëüíîé ñòðîêå.Ôîðìàëüíî, ïóñòüG = (N, Σ, P, A1 ), ãäå N = ([Σ∪{e}]×Γ)∪Q∪{A1 , A2 , A3 }Ïðîäóêöèè P òàêîâû:1.
A1 → q0 A2 .2. A2 → [a, a]A2 äëÿ êàæäîãî a ∈ Σ.3. A2 → A3 .4. A3 → [e, B]A3 .5. A3 → e.6. q[a, C] → [a, E]p äëÿ êàæäîãî a ∈ Σ ∪ {e} è êàæäîãîq ∈ Q è C ∈ Γ òàêîãî, ÷òî D(q, C) = (p, E, R).7. [b, I]q[a, C] → p[b, I][a, J] äëÿ êàæäîãî C, J, I èç Γ, a èb èç Σ ∪ {e} è q èç Q òàêèõ, ÷òî D(q, C) = (p, J, L).8. [a, C]q → qaq, q[a, C] → qaq, q → eäëÿ êàæäîãî a ∈ Σ ∪ {e}, C ∈ Γ, q ∈ F.Ñâÿçü ìàøèí Òüþðèíãà è ãðàììàòèê òèïà 037Èñïîëüçóÿ ïðàâèëà 1 è 2,A1 ⇒∗ q0 [a1 , a1 ][a2 , a2 ] ... [an , an ]A2 ,ãäå ai ∈ Σ äëÿ íåêîòîðîãî i.Ïðåäïîëîæèì, ÷òî T m äîïóñêàåò ñòðîêó a1 a2 ... an .
Òîãäà äëÿ íåêîòîðîãî m T m èñïîëüçóåò íå áîëåå, ÷åì m ÿ÷ååêñïðàâà îò âõîäà. Èñïîëüçóÿ ïðàâèëî 3, çàòåì ïðàâèëî 4 mðàç, è íàêîíåö, ïðàâèëî 5, èìååìA1 ⇒∗ q0 [a1 , a1 ][a2 , a2 ] ... [an , an ][e, B]m .Íà÷èíàÿ ñ ýòîãî ìîìåíòà ìîãóò áûòü èñïîëüçîâàíûòîëüêî ïðàâèëà 6 è 7, ïîêà íå ñãåíåðèðóåòñÿ äîïóñêàþùååñîñòîÿíèå. Îòìåòèì, ÷òî ïåðâûå êîìïîíåíòû ëåíòî÷íûõñèìâîëîâ â (Σ ∪ {e}) × Γ íèêîãäà íå ìåíÿþòñÿ. Èíäóêöèåéïî ÷èñëó øàãîâ T m ìîæíî ïîêàçàòü, ÷òî åñëè(q0 , a1 a2 ... an , 1) |−T m∗ (q, X1 X2 ...
Xs , r),òîmq0 [a1 , a1 ][a2 , a2 ] ... [an , an ][e, B] ⇒G∗⇒G∗ [a1 , X1 ][a2 , X2 ] ... [ar−1 , Xr−1 ]q[ar , Xr ] ... [an+m , Xn+m ],ãäå a1 , a2 , ... an ïðèíàäëåæàò Σ, an+1 = an+2 = ... an+m = e,X1 , X2 ,...Xn+m ïðèíàäëåæàò Γ è Xs+1 =Xs+2 =...Xn+m =B .Ïðåäïîëîæåíèå èíäóêöèè òðèâèàëüíî äëÿ íóëÿ øàãîâ.Ïðåäïîëîæèì, ÷òî îíî ñïðàâåäëèâî äëÿ k − 1 øàãîâ. Ïóñòü(q0 , a1 a2 ... an , 1) `T m∗`T m∗ (q1 , X1 X2 ...
Xr , j1 ) `T m`T m (q2 , Y1 Y2 ... Ys , j2 )çà k øàãîâ. Ïî ïðåäïîëîæåíèþ èíäóêöèèq0 [a1 , a1 ][a2 , a2 ] ... [an , an ][e, B]m ⇒G∗⇒G∗ [a1 , X1 ][a2 , X2 ] ... [ar−1 , Xr−1 ]q1 [aj1 , Xj1 ] ...... [an+m , Xn+m ].Ïóñòü E = L, åñëè j2 = j1 − 1 è E = R, åñëè j2 = j1 + 1. ýòîì ñëó÷àå D(q1 , Xj1 ) = (q2 , Yj1 , E).Ïî ïðàâèëàì 6 èëè 7q1 [aj1 , Xj1 ] → [aj1 , Yj1 ]q2èëè[aj1 −1 , Xj1 −1 ]q1 [aj1 , Xj1 ] → q2 [aj1 −1 , Xj1 −1 ][aj1 , Yj1 ],â çàâèñèìîñòè îò òîãî, ðàâíî ëè E çíà÷åíèþ R èëè L.Òåïåðü Xi = Yi äëÿ âñåõ i 6= j1 .Òàêèì îáðàçîì,q0 [a1 , a1 ][a2 , a2 ] ... [an , an ][e, B]m ⇒G∗38Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèå⇒G∗ [a1 , Y1 ]q2 [aj2 , Yj2 ] ... [an+m , Yn+m ],÷òî äîêàçûâàåò ïðåäïîëîæåíèå èíäóêöèè.Ïî ïðàâèëó 8, åñëè q ∈ F , ëåãêî ïîêàçàòü, ÷òî[a1 , X1 ] ... q[aj , Xj ] ... [an+m , Xn+m ] ⇒∗ a1 a2 ...
an .Òàêèì îáðàçîì, G ìîæåò ãåíåðèðîâàòü a1 a2 ... an , åñëèa1 a2 ... an äîïóñêàåòñÿ T m. Òàêèì îáðàçîì, L(G) âêëþ÷àåòâñå ñëîâà, äîïóñêàåìûå T m. Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà íåîáõîäèìî ïîêàçàòü, ÷òî âñå ñëîâà èç L(G) äîïóñêàþòñÿ T m. Èíäóêöèåé äîêàçûâàåòñÿ, ÷òî A1 ⇒G∗ w òîëüêîåñëè w äîïóñêàåòñÿ T m.2.6. Ëèíåéíî-îãðàíè÷åííûå àâòîìàòû è èõ ñâÿçü ñ êîíòåêñòíîçàâèñèìûìè ãðàììàòèêàìèÊàæäûé ÊÇ-ÿçûê ÿâëÿåòñÿ ðåêóðñèâíûì, íî îáðàòíîåíå âåðíî. Ïîêàæåì ÷òî ñóùåñòâóåò àëãîðèòì, ïîçâîëÿþùèéäëÿ ïðîèçâîëüíîãî ÊÇ-ÿçûêà L â àëôàâèòå T , è ïðîèçâîëüíîé öåïî÷êè w ∈ T ∗ îïðåäåëèòü, ïðèíàäëåæèò ëè w ÿçûêóL.Òåîðåìà 2.6.
Êàæäûé êîíòåêñòíî-çàâèñèìûé ÿçûêÿâëÿåòñÿ ðåêóðñèâíûì ÿçûêîì.Äîêàçàòåëüñòâî. Ïóñòü L êîíòåêñòíî-çàâèñèìûé ÿçûê.Òîãäà ñóùåñòâóåò íåêîòîðàÿ íåóêîðà÷èâàþùàÿ ãðàììàòèêàG = (N, T, P, S), ïîðîæäàþùàÿ L.Ïóñòü w ∈ T ∗ è |w| = n. Åñëè n = 0, òî åñòü w = e, òîïðèíàäëåæíîñòü w ∈ L ïðîâåðÿåòñÿ òðèâèàëüíûì îáðàçîì.Òàê ÷òî áóäåì ïðåäïîëàãàòü, ÷òî n > 0.Îïðåäåëèì ìíîæåñòâî Tm êàê ìíîæåñòâî ñòðîê u ∈ (N ∪T )+ äëèíû íå áîëåå n òàêèõ, ÷òî âûâîä S ⇒∗ u èìååò íåáîëåå m øàãîâ. ßñíî, ÷òî T0 = {S}.Ñâÿçü ëèíåéíî-îãðàíè÷åííûõ àâòîìàòîâ è ÊÇ-ÿçûêîâ39Ëåãêî ïîêàçàòü, ÷òî Tm ìîæíî ïîëó÷èòü èç Tm−1 ïðîñìàòðèâàÿ, êàêèå ñòðîêè ñ äëèíîé, ìåíüøåé èëè ðàâíîé nìîæíî âûâåñòè èç ñòðîê èç Tm−1 ïðèìåíåíèåì îäíîãî ïðàâèëà, òî åñòüTm = Tm−1 ∪{u | v ⇒ u äëÿ íåêîòîðîãî v ∈ Tm−1 , ãäå |u| 6 n}.Åñëè S ⇒∗ u è |u| 6 n, òî u ∈ Tm äëÿ íåêîòîðîãî m.Åñëè èç S íå âûâîäèòñÿ u èëè |u| > n, òî u íå ïðèíàäëåæèòTm íè äëÿ êàêîãî m.Î÷åâèäíî, ÷òî Tm ⊇ Tm−1 äëÿ âñåõ m > 1.
ÏîñêîëüêóTm çàâèñèò òîëüêî îò Tm−1 , åñëè Tm = Tm−1 , òî Tm =Tm+1 = Tm+2 = . . . . Ïðîöåäóðà áóäåò âû÷èñëÿòü T1 , T2 , T3 ,. . . ïîêà äëÿ íåêîòîðîãî m íå îêàæåòñÿ Tm = Tm−1 . Åñëè wíå ïðèíàäëåæèò Tm , òî íå ïðèíàäëåæèò è L(G), ïîñêîëüêóäëÿ j > m âûïîëíåíî Tj = Tm . Åñëè w ∈ Tm , òî S ⇒∗ w.Ïîêàæåì, ÷òî ñóùåñòâóåò òàêîå m, ÷òî Tm = Tm−1 .Ïîñêîëüêó äëÿ êàæäîãî i > 1 ñïðàâåäëèâî Ti ⊇Ti−1 , òî åñëè Ti 6= Ti−1 , òî ÷èñëî ýëåìåíòîâ â Tiïî êðàéíåé ìåðå íà 1 áîëüøå, ÷åì â Ti−1 . Ïóñòü|N ∪ T | = k . Òîãäà ÷èñëî ñòðîê â (N ∪ T )+ äëèíû ìåíüøåé èëè ðàâíîé n ðàâíî k + k 2 + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
