В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 10
Текст из файла (страница 10)
. . , pn , è ïóñòü S =f ollowpos(pi );if (S 6= ∅){if (S ∈/ Q)}}16i6näîáàâèòü S â Q êàê íåïîìå÷åííîåñîñòîÿíèå;îïðåäåëèòü D(R, a) = S ;}(6) Îïðåäåëèòü F êàê ìíîæåñòâî âñåõ ñîñòîÿíèé èç Q,ñîäåðæàùèõ ïîçèöèè, ñâÿçàííûå ñ ñèìâîëîì #.3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõ àâòîìàòîâ63Ïðèìåð 3.9. Ðåçóëüòàò ïðèìåíåíèÿ àëãîðèòìà 3.3 äëÿ ðåãóëÿðíîãî âûðàæåíèÿ (a|b)∗ abb ïðèâåä¼í íà ðèñ. 3.14.EDD^`ED^`E^`E^`DÐèñ.
3.14.3.3.4. Ïîñòðîåíèå äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ñ ìèíèìàëüíûì÷èñëîì ñîñòîÿíèéÐàññìîòðèì òåïåðü àëãîðèòì ïîñòðîåíèÿ ÄÊÀ ñ ìèíèìàëüíûì ÷èñëîì ñîñòîÿíèé, ýêâèâàëåíòíîãî äàííîìóÄÊÀ [3].Ïóñòü M = (Q, T, D, q0 , F ) ÄÊÀ. Áóäåì íàçûâàòü Mâñþäó îïðåäåë¼ííûì, åñëè D(q, a) 6= ∅ äëÿ âñåõ q ∈ Q èa ∈ T.Ëåììà. Ïóñòü M = (Q, T, D, q0 , F ) ÄÊÀ, íå ÿâëÿþùèéñÿ âñþäó îïðåäåë¼ííûì.
Ñóùåñòâóåò âñþäó îïðåäåë¼ííûé ÄÊÀ M 0 , òàêîé ÷òî L(M ) = L(M 0 ).Äîêàçàòåëüñòâî. Ðàññìîòðèì àâòîìàòM 0 = (Q ∪ {q 0 }, T, D0 , q0 , F ),ãäå q 0 ∈/ Q íåêîòîðîå íîâîå ñîñòîÿíèå, à ôóíêöèÿ D0 îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:(1) Äëÿ âñåõ q ∈ Q è a ∈ T , òàêèõ ÷òî D(q, a) 6= ∅, îïðåäåëèòü D0 (q, a) = D(q, a).64Ãëàâà 3. Ëåêñè÷åñêèé àíàëèç(2) Äëÿ âñåõ q ∈ Q è a ∈ T , òàêèõ ÷òî D(q, a) = ∅, îïðåäåëèòü D0 (q, a) = q 0 .(3) Äëÿ âñåõ a ∈ T îïðåäåëèòü D0 (q 0 , a) = q 0 .Ëåãêî ïîêàçàòü, ÷òî àâòîìàò M 0 äîïóñêàåò òîò æå ÿçûê,÷òî è M .Ïðèâåä¼ííûé íèæå àëãîðèòì ïîëó÷àåò íà âõîäå âñþäóîïðåäåë¼ííûé àâòîìàò. Åñëè àâòîìàò íå ÿâëÿåòñÿ âñþäóîïðåäåë¼ííûì, åãî ìîæíî ñäåëàòü òàêîâûì íà îñíîâàíèèòîëüêî ÷òî ïðèâåä¼ííîé ëåììû.Àëãîðèòì 3.4. Ïîñòðîåíèå ÄÊÀ ñ ìèíèìàëüíûì ÷èñëîì ñîñòîÿíèé.Âõîä.
Âñþäó îïðåäåë¼ííûé ÄÊÀ M = (Q, T, D, q0 , F ).Âûõîä. ÄÊÀ M 0 = (Q0 , T, D0 , q00 , F 0 ), òàêîé ÷òî L(M ) =L(M 0 ) è M 0 ñîäåðæèò íàèìåíüøåå âîçìîæíîå ÷èñëî ñîñòîÿíèé.Ìåòîä. Âûïîëíèòü øàãè 1-5:(1) Ïîñòðîèòü íà÷àëüíîå ðàçáèåíèå Π ìíîæåñòâà ñîñòîÿíèé èç äâóõ ãðóïï: çàêëþ÷èòåëüíûå ñîñòîÿíèÿ F èîñòàëüíûå Q − F , òî åñòü Π = {F, Q − F }.(2) Ïðèìåíèòü ê Π ñëåäóþùóþ ïðîöåäóðó è ïîëó÷èòü íîâîå ðàçáèåíèå Πnew :for (êàæäîé ãðóïïû G â Π){ðàçáèòü G íà ïîäãðóïïû òàê, ÷òîáûñîñòîÿíèÿ s è t èç G îêàçàëèñüâ îäíîé ïîäãðóïïå òîãäà è òîëüêî òîãäà,êîãäà äëÿ êàæäîãî âõîäíîãî ñèìâîëà añîñòîÿíèÿ s è t èìåþò ïåðåõîäû ïî aâ ñîñòîÿíèÿ èç îäíîé è òîé æå ãðóïïû â Π;çàìåíèòü G â Πnew íà ìíîæåñòâî âñåõïîëó÷åííûõ ïîäãðóïï;}(3) Åñëè Πnew = Π, ïîëàãàåì Πres = Π è ïåðåõîäèì ê øàãó4, èíà÷å ïîâòîðÿåì øàã 2 ñ Π := Πnew .(4) Ïóñòü Πres = {G1 , .
. . , Gn }. Îïðåäåëèì:3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõ àâòîìàòîâ65Q0 = {G1 , . . . , Gn };q00 = G, ãäå ãðóïïà G ∈ Q0 òàêîâà, ÷òî q0 ∈ G;F 0 = {G|G ∈ Q0 è G ∩ F 6= ∅};D0 (p0 , a) = q 0 , åñëè D(p, a) = q , ãäå p ∈ p0 è q ∈ q 0 .Òàêèì îáðàçîì, êàæäàÿ ãðóïïà â Πres ñòàíîâèòñÿ ñîñòîÿíèåì íîâîãî àâòîìàòà M 0 .
Åñëè ãðóïïà ñîäåðæèòíà÷àëüíîå ñîñòîÿíèå àâòîìàòà M , òî ýòà ãðóïïà ñòàíîâèòñÿ íà÷àëüíûì ñîñòîÿíèåì àâòîìàòà M 0 . Åñëè ãðóïïà ñîäåðæèò çàêëþ÷èòåëüíîå ñîñòîÿíèå M , îíà ñòàíîâèòñÿ çàêëþ÷èòåëüíûì ñîñòîÿíèåì M 0 . Îòìåòèì, ÷òîêàæäàÿ ãðóïïà Πres ëèáî ñîñòîèò òîëüêî èç ñîñòîÿíèéèç F , ëèáî íå èìååò ñîñòîÿíèé èç F . Ïåðåõîäû îïðåäåëÿþòñÿ î÷åâèäíûì îáðàçîì.(5) Åñëè M 0 èìååò ¾ì¼ðòâîå¿ ñîñòîÿíèå, òî åñòü ñîñòîÿíèå, êîòîðîå íå ÿâëÿåòñÿ äîïóñêàþùèì è èç êîòîðîãîíåò ïóòåé â äîïóñêàþùèå, óäàëèòü åãî è ñâÿçàííûå ñíèì ïåðåõîäû èç M 0 . Óäàëèòü èç M 0 òàêæå âñå ñîñòîÿíèÿ, íåäîñòèæèìûå èç íà÷àëüíîãî.Ïðèìåð 3.10.
Ðåçóëüòàò ïðèìåíåíèÿ àëãîðèòìà 3.4 ïðèâå-ä¼í íà ðèñ. 3.15.EDEDEDEDED^`ED^` E ^`DEEÐèñ. 3.15.D66Ãëàâà 3. Ëåêñè÷åñêèé àíàëèç3.4. Ñâÿçü ðåãóëÿðíûõ ìíîæåñòâ,êîíå÷íûõ àâòîìàòîâ è ðåãóëÿðíûõ ãðàììàòèê ðàçäåëå 3.3.3 ïðèâåä¼í àëãîðèòì ïîñòðîåíèÿ äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ïî ðåãóëÿðíîìó âûðàæåíèþ. Ðàññìîòðèì òåïåðü êàê ïî îïèñàíèþ êîíå÷íîãî àâòîìàòà ïîñòðîèòü ðåãóëÿðíîå ìíîæåñòâî, ñîâïàäàþùåå ñ ÿçûêîì, äîïóñêàåìûì êîíå÷íûì àâòîìàòîì.Òåîðåìà 3.1. ßçûê, äîïóñêàåìûé äåòåðìèíèðîâàííûìêîíå÷íûì àâòîìàòîì, ÿâëÿåòñÿ ðåãóëÿðíûì ìíîæåñòâîì.Äîêàçàòåëüñòâî. Ïóñòü L ÿçûê, äîïóñêàåìûé äåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîìM =({q1 , . . . , qn }, T, D, q1 , F ).eÂâåä¼ì D ðàñøèðåííóþ ôóíêöèþ ïåðåõîäîâ àâòîìàòà M : De (q, w) = p, ãäå w ∈ T ∗ , òîãäà è òîëüêî òîãäà, êîãäà(q, w) `∗ (p, e).kÎáîçíà÷èì ïîñðåäñòâîì Rijìíîæåñòâî âñåõ ñëîâ x òàeêèõ, ÷òî D (qi , x) = qj è åñëè De (qi , y) = qs äëÿ ëþáîéöåïî÷êè y ïðåôèêñà x, îòëè÷íîãî îò x è e, òî s 6 k .kåñòü ìíîæåñòâî âñåõ ñëîâ, êîòîðûåÈíûìè ñëîâàìè, Rijïåðåâîäÿò êîíå÷íûé àâòîìàò èç ñîñòîÿíèÿ qi â ñîñòîÿíèå qj ,íå ïðîõîäÿ íè ÷åðåç êàêîå ñîñòîÿíèå qs äëÿ s > k .
Îäíàêî,i è j ìîãóò áûòü áîëüøå k .kRijìîæåò áûòü îïðåäåëåíî ðåêóðñèâíî ñëåäóþùèì îáðàçîì:0Rij= {a|a ∈ T, D(qi , a) = qj },k−1 S k−1k−1 ∗ k−1kRij = RijRik (Rkk) Rkj , ãäå 1 6 k 6 n.kÒàêèì îáðàçîì, îïðåäåëåíèå Rijîçíà÷àåò, ÷òî äëÿ âõîäíîé öåïî÷êè w, ïåðåâîäÿùåé M èç qi â qj áåç ïåðåõîäà ÷åðåçñîñòîÿíèÿ ñ íîìåðàìè, áîëüøèìè k , ñïðàâåäëèâî ðîâíî îäíî èç ñëåäóþùèõ äâóõ óòâåðæäåíèé:3.4. Ñâÿçü ðåã. ìíîæåñòâ, ÊÀ è ðåã. ãðàììàòèê67k−11. Öåïî÷êà w ïðèíàäëåæèò Rij, òî åñòü ïðè àíàëèçåöåïî÷êè w àâòîìàò íèêîãäà íå äîñòèãàåò ñîñòîÿíèé ñíîìåðàìè, áîëüøèìè èëè ðàâíûìè k .2. Öåïî÷êà w ìîæåò áûòü ïðåäñòàâëåíà êàê w=w1 w2 w3 ,k−1ãäå w1 ∈ Rik(ïîäöåïî÷êà w1 ïåðåâîäèò M ñíà÷àëà âk−1 ∗qk ), w2 ∈ (Rkk) (ïîäöåïî÷êà w2 ïåðåâîäèò M èç qkîáðàòíî â qk , íå ïðîõîäÿ ÷åðåç ñîñòîÿíèÿ ñ íîìåðàìè,k−1áîëüøèìè èëè ðàâíûìè k ), è w3 ∈ Rkj(ïîäöåïî÷êàw3 ïåðåâîäèò M èç ñîñòîÿíèÿ qk â qj ) ðèñ. 3.16.TNTLT VV N T MÐèñ.
3.16.Òîãäà L =Sqj ∈FnR1j. Èíäóêöèåé ïî k ìîæíî ïîêàçàòü,÷òî ýòî ìíîæåñòâî ÿâëÿåòñÿ ðåãóëÿðíûì.Òàêèì îáðàçîì, äëÿ âñÿêîãî ðåãóëÿðíîãî ìíîæåñòâà èìååòñÿ êîíå÷íûé àâòîìàò, äîïóñêàþùèé â òî÷íîñòè ýòî ðåãóëÿðíîå ìíîæåñòâî, è íàîáîðîò ÿçûê, äîïóñêàåìûé êîíå÷íûì àâòîìàòîì åñòü ðåãóëÿðíîå ìíîæåñòâî.Ðàññìîòðèì òåïåðü ñîîòíîøåíèå ìåæäó ÿçûêàìè, ïîðîæäàåìûìè ïðàâîëèíåéíûìè ãðàììàòèêàìè è äîïóñêàåìûìè êîíå÷íûìè àâòîìàòàìè.Ïðàâîëèíåéíàÿ ãðàììàòèêà G = (N, T, P, S) íàçûâàåòñÿðåãóëÿðíîé, åñëè68Ãëàâà 3.
Ëåêñè÷åñêèé àíàëèç(1) êàæäîå å¼ ïðàâèëî, êðîìå S → e, èìååò âèä ëèáîA → aB , ëèáî A → a, ãäå A, B ∈ N , a ∈ T ;(2) â òîì ñëó÷àå, êîãäà S → e ∈ P , íà÷àëüíûé ñèìâîë Síå âñòðå÷àåòñÿ â ïðàâûõ ÷àñòÿõ ïðàâèë.Ëåììà. Ïóñòü G ïðàâîëèíåéíàÿ ãðàììàòèêà. Ñóùåñòâóåò ðåãóëÿðíàÿ ãðàììàòèêà G0 òàêàÿ, ÷òî L(G) =L(G0 ).Äîêàçàòåëüñòâî. Ïðåäîñòàâëÿåòñÿ ÷èòàòåëþ â êà÷åñòâåóïðàæíåíèÿ.Òåîðåìà 3.2. Ïóñòü G = (N, T, P, S) ïðàâîëèíåéíàÿ ãðàììàòèêà. Òîãäà ñóùåñòâóåò êîíå÷íûé àâòîìàò M = (Q, T, D, q0 , F ) äëÿ êîòîðîãî L(M ) = L(G).Äîêàçàòåëüñòâî.
Íà îñíîâàíèè ïðèâåä¼ííîé âûøå ëåììû, áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî G ðåãóëÿðíàÿ ãðàììàòèêà.Ïîñòðîèì ÍÊÀ M ñëåäóþùèì îáðàçîì:1. ñîñòîÿíèÿìè M áóäóò íåòåðìèíàëû G ïëþñ íîâîåñîñòîÿíèå R, íå ïðèíàäëåæàùåå N . Òàê ÷òî Q =N ∪ {R};2. â êà÷åñòâå íà÷àëüíîãî ñîñòîÿíèÿ M ïðèìåì S , òî åñòüq0 = S ;3. åñëè P ñîäåðæèò ïðàâèëî S → e, òî F = {S, R}, èíà÷åF = {R}. Íàïîìíèì, ÷òî S íå âñòðå÷àåòñÿ â ïðàâûõ÷àñòÿõ ïðàâèë, åñëè S → e ∈ P ;4.
ñîñòîÿíèå R ∈ D(A, a), åñëè A → a ∈ P . Êðîìå òîãî, D(A, a) ñîäåðæèò âñå B òàêèå, ÷òî A → aB ∈ P .D(R, a) = ∅ äëÿ êàæäîãî a ∈ T .M , ÷èòàÿ âõîä w, ìîäåëèðóåò âûâîä w â ãðàììàòèêå G.Ïîêàæåì, ÷òî L(M ) = L(G). Ïóñòü w = a1 a2 . . . an ∈ L(G),n > 1.
Òîãäà S ⇒ a1 A1 ⇒ . . . ⇒ a1 a2 . . . an−1 An−1 ⇒a1 a2 . . . an−1 an äëÿ íåêîòîðîé ïîñëåäîâàòåëüíîñòè íåòåðìèíàëîâ A1 , A2 , . . . , An−1 . Ïî îïðåäåëåíèþ, D(S, a1 ) ñîäåðæèò A1 , D(A1 , a2 ) ñîäåðæèò A2 , è ò.ä., D(An−1 , an ) ñîäåðæèò R. Òàê ÷òî w ∈ L(M ), ïîñêîëüêó De (S, w) ñîäåðæèòR, à R ∈ F . Åñëè e ∈ L(G), òî S ∈ F , òàê ÷òî e ∈ L(M ).3.4. Ñâÿçü ðåã. ìíîæåñòâ, ÊÀ è ðåã.
ãðàììàòèê69Àíàëîãè÷íî, åñëè w=a1 a2 . . . an ∈ L(M ),n > 1, òî ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü ñîñòîÿíèéS, A1 , A2 , . . . , An−1 , R òàêàÿ, ÷òî D(S, a1 ) ñîäåðæèò A1 ,D(A1 , a2 ) ñîäåðæèò A2 , è ò.ä. Ïîýòîìó S ⇒ a1 A1 ⇒a1 a2 A2 ⇒ . . . ⇒ a1 a2 . . . an−1 An−1 ⇒ a1 a2 . . . an−1 an âûâîä â G è x ∈ L(G). Åñëè e ∈ L(M ), òî S ∈ F , òàê ÷òîS → e ∈ P è e ∈ L(G).Òåîðåìà 3.3. Äëÿ êàæäîãî êîíå÷íîãî àâòîìàòà M =(Q, T, D, q0 , F ) ñóùåñòâóåò ïðàâîëèíåéíàÿ ãðàììàòèêà G = (N, T, P, S) òàêàÿ, ÷òî L(G) = L(M ).Äîêàçàòåëüñòâî. Áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü,÷òî àâòîìàò M äåòåðìèíèðîâàííûé.
Îïðåäåëèì ãðàììàòèêó G ñëåäóþùèì îáðàçîì:1. íåòåðìèíàëàìè ãðàììàòèêè G áóäóò ñîñòîÿíèÿ àâòîìàòà M . Òàê ÷òî N = Q;2. â êà÷åñòâå íà÷àëüíîãî ñèìâîëà ãðàììàòèêè G ïðèìåìq0 , òî åñòü S = q0 ;3. A → aB ∈ P , åñëè D(A, a) = B ;4. A → a ∈ P , åñëè D(A, a) = B è B ∈ F ;5. S → e ∈ P , åñëè q0 ∈ F .Äîêàçàòåëüñòâî òîãî, ÷òî S ⇒∗ w òîãäà è òîëüêî òîãäà,êîãäà De (q0 , w) ∈ F , àíàëîãè÷íî äîêàçàòåëüñòâó òåîðåìû 3.2. íåêîòîðûõ ñëó÷àÿõ äëÿ îïðåäåëåíèÿ òîãî, ÿâëÿåòñÿëè ÿçûê ðåãóëÿðíûì, ìîæåò áûòü ïîëåçíûì íåîáõîäèìîåóñëîâèå, êîòîðîå íàçûâàåòñÿ ëåììîé Îãäåíà î ðàçðàñòàíèè.Òåîðåìà 3.4. (Ëåììà î ðàçðàñòàíèè äëÿ ðåãóëÿðíûõìíîæåñòâ). Ïóñòü L - ðåãóëÿðíîå ìíîæåñòâî. Ñóùåñòâóåò òàêàÿ êîíñòàíòà k , ÷òî åñëè w ∈ L è |w| > k,òî öåïî÷êó w ìîæíî ïðåäñòàâèòü â âèäå xyz , ãäå0 < |y| 6 k è xy i z ∈ L äëÿ âñåõ i > 0.70Ãëàâà 3. Ëåêñè÷åñêèé àíàëèçÄîêàçàòåëüñòâî.
Ïóñòü M = (Q, Σ, D, q0 , F ) - êîíå÷íûéàâòîìàò, äîïóñêàþùèé L, òî åñòü L(M ) = L è k = |Q|.Ïóñòü w ∈ L è |w| > k . Ðàññìîòðèì ïîñëåäîâàòåëüíîñòüêîíôèãóðàöèé, êîòîðûå ïðîõîäèò àâòîìàò M , äîïóñêàÿ öåïî÷êó w. Òàê êàê â íåé ïî êðàéíåé ìåðå k + 1 êîíôèãóðàöèÿ, òî ñðåäè ïåðâûõ k + 1 êîíôèãóðàöèè íàéäóòñÿ äâåñ îäèíàêîâûìè ñîñòîÿíèÿìè. Òàêèì îáðàçîì, ïîëó÷àåì ñóùåñòâîâàíèå òàêîé ïîñëåäîâàòåëüíîñòè òàêòîâ, ÷òî(q0 , xyz) |−∗ (q1 , yz) |−r (q1 , z) |−∗ (q2 , e)äëÿ íåêîòîðûõ q1 ∈ Q, q2 ∈ F è 0 < r 6 k . Îòñþäà0 < |y| 6 n.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
