1610906281-d25a58898a45262b0b837c281ba962eb (Лекции Когабаев Соболева), страница 7

Ðåãóëÿðíûå ÿçûêè äàëüíåéøåì ìû áóäåì îïóñêàòü íåêîòîðûå (â òîì ÷èñëå âíåøíèå)ñêîáêè ïðè çàïèñè ðåãóëÿðíûõ âûðàæåíèé, êàê ýòî äåëàåòñÿ â îáû÷íîé àëãåáðå,ñ÷èòàÿ, ÷òî îïåðàöèè èìåþò ñëåäóþùèé ïðèîðèòåò: α∗ ñàìàÿ ñèëüíàÿ îïåðàöèÿ,äàëåå èä¼ò αβ , à îïåðàöèÿ α ∪β ñàìàÿ ñëàáàÿ. Íàïðèìåð, çàïèñü α∗ β ∪βα íà ñàìîìäåëå îçíà÷àåò (((α∗ )β) ∪ (βα)).Çàìå÷àíèå.Îïðåäåëåíèå. Îïðåäåëèì îòîáðàæåíèå L èç ìíîæåñòâà âñåõ ðåãóëÿðíûõ âûðàæåíèé íàä àëôàâèòîì A â ìíîæåñòâî âñåõ ÿçûêîâ íàä A ñëåäóþùèì îáðàçîì:L(∅) = ∅,L(a) = {a}, äëÿ ëþáîãî a ∈ A,L(αβ) = L(α)L(β),L(α ∪ β) = L(α) ∪ L(β),L(α∗ ) = L(α)∗ .ðåãóëÿðíûìßçûê L íàä àëôàâèòîì A íàçûâàåòñÿ, åñëè ñóùåñòâóåòðåãóëÿðíîå âûðàæåíèå α íàä àëôàâèòîì A òàêîå, ÷òî L(α) = L.

Ïðè ýòîì áóäåìãîâîðèòü, ÷òî âûðàæåíèå αÿçûê L.Îïðåäåëåíèå.çàäà¼òÈç òîæäåñòâà ∅∗ = {Λ} ñëåäóåò, ÷òî ÿçûê {Λ}, ñîñòîÿùèé èç îäíîãîïóñòîãî ñëîâà, ðåãóëÿðåí.Çàìå÷àíèå.ßçûê L = {w ∈ {a, b}∗ | w ñîäåðæèò ïîäñëîâî bb} ÿâëÿåòñÿ ðåãóëÿðíûì,ïîñêîëüêó åãî ìîæíî çàäàòü ðåãóëÿðíûì âûðàæåíèåì (a∗ ∪ba)∗ bb(a∪b)∗ . Çàìåòèì, ÷òîäëÿ ëþáîãî ðåãóëÿðíîãî ÿçûêà ñóùåñòâóåò áåñêîíå÷íî ìíîãî ðåãóëÿðíûõ âûðàæåíèé,çàäàþùèõ åãî. Íàïðèìåð, òîò æå ÿçûê L ìîæíî çàäàòü ðåãóëÿðíûì âûðàæåíèåì(a ∪ b)∗ bb(a ∪ b)∗ .Ïðèìåð.Êëàññ àâòîìàòíûõ ÿçûêîâ ñîâïàäàåò ñ êëàññîì ðåãóëÿðíûõ ÿçûêîâ.Äîêàçàòåëüñòâî.

Ñíà÷àëà äîêàæåì, ÷òî ëþáîé ðåãóëÿðíûé ÿçûê àâòîìàòåí. ÏóñòüÒåîðåìà 14.L ðåãóëÿðíûé ÿçûê íàä àëôàâèòîì A. Ñëåäîâàòåëüíî, íàéä¼òñÿ õîòÿ áû îäíî ðåãóëÿðíîå âûðàæåíèå γ , êîòîðîå çàäà¼ò L. Èíäóêöèåé ïî äëèíå âûðàæåíèÿ γ äîêàæåì,÷òî L àâòîìàòíûé.10 . Åñëè γ ÿâëÿåòñÿ âûðàæåíèåì âèäà ∅ èëè a, ãäå a ∈ A, ò. å. L = ∅ èëè L = {a},òî â ñèëó òåîðåìû 11 ÿçûê L ÿâëÿåòñÿ àâòîìàòíûì.20 . Åñëè γ ÿâëÿåòñÿ âûðàæåíèåì âèäà (αβ), (α ∪ β) èëè (α∗ ), ãäå α, β ðåãóëÿðíûå, òî ïî èíäóêöèîííîìó ïðåäïîëîæåíèþ çàêëþ÷àåì, ÷òî ÿçûêè L1 = L(α)è L2 = L(β) àâòîìàòíûå. Òîãäà L = L1 L2 , èëè L = L1 ∪ L2 , èëè L = L∗1ñîîòâåòñòâåííî.

 ëþáîì ñëó÷àå ïî òåîðåìå 10 ïîëó÷àåì, ÷òî L àâòîìàòåí.Òåïåðü äîêàæåì, ÷òî ëþáîé àâòîìàòíûé ÿçûê ðåãóëÿðåí. Ïóñòü L ïðîèçâîëüíûé àâòîìàòíûé ÿçûê. Ñëåäîâàòåëüíî, ñóùåñòâóåò ä.ê.à. A = hQ, A, δ, q1 , F i ñ ñîñòîÿíèìè Q = {q1 , . . . , qn } òàêîé, ÷òî L(A) = L. Äîêàæåì, ÷òî L ðåãóëÿðíûé. Äëÿýòîãî îïðåäåëèì äëÿ âñåõ 1 6 i 6 n, 1 6 j 6 n è 0 6 k 6 n ìíîæåñòâî ñëîâ:R(i, j, k) = {w ∈ A∗ | w ÷èòàåòñÿ âäîëü ïóòè àâòîìàòà A, êîòîðûéíà÷èíàåòñÿ â qi , çàêàí÷èâàåòñÿ â qj è êîòîðûé â ïðîìåæóòêåìåæäó íèìè íå çàõîäèò â ñîñòîÿíèÿ qk+1 , qk+2 , .

. . , qn }.28Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêè(Çäåñü òåðìèíîì ¾ïðîìåæóòîê ìåæäó qi è qj ¿ ìû íàçûâàåì ìíîæåñòâî âñåõ ñîñòîÿíèé ïóòè, èñêëþ÷àÿ åãî íà÷àëî qi è åãî êîíåö qj . Íàïîìíèì òàêæå, ÷òî ïóñòîå ñëîâîΛ ïî îïðåäåëåíèþ ÷èòàåòñÿ âäîëü ïóòè, êîòîðûé ñîäåðæèò òîëüêî îäíî ñîñòîÿíèå èíå ñîäåðæèò íè îäíîé äóãè.)Çàìåòèì, ÷òî ïðè k = n ìíîæåñòâî R(i, j, n) ñîñòîèò â òî÷íîñòè èç âñåõ ñëîâ,÷èòàåìûõ âäîëü ïóòåé íàøåãî àâòîìàòà, èäóùèõ èç qi â qj .

Êðîìå ýòîãî, ÿñíî, ÷òî[L = L(A) =R(1, j, n).qj ∈FÒàê êàê ðåãóëÿðíûå ÿçûêè çàìêíóòû îòíîñèòåëüíî îáúåäèíåíèÿ, òî äîñòàòî÷íî äîêàçàòü, ÷òî âñå R(i, j, k) ðåãóëÿðíû. Äîêàæåì ýòî óòâåðæäåíèå èíäóêöèåé ïî k .10 . Ïðè k = 0 ìíîæåñòâî R(i, j, 0) ýòî âñå ñëîâà, ÷èòàåìûå âäîëü îäíîé äóãè,âåäóùåé èç qi â qj . Âîçìîæíû òðè ñëó÷àÿ. Åñëè òàêàÿ äóãà ñóùåñòâóåò è îíàïîìå÷åíà ñèìâîëîì a, òî R(i, j, 0) = {a}. Åñëè òàêîé äóãè íåò è qi = qj , òîR(i, j, 0) = {Λ}. Åñëè òàêîé äóãè íåò è qi 6= qj , òî R(i, j, 0) = ∅.

Âñå òàêèåÿçûêè ðåãóëÿðíû, â ñèëó îïðåäåëåíèÿ è çàìå÷àíèÿ î ÿçûêå {Λ}.20 . Äîïóñòèì, ÷òî óòâåðæäåíèå äîêàçàíî äëÿ k − 1, ò. å. âñå ÿçûêè R(i, j, k − 1)ðåãóëÿðíû. Ðàññìîòðèì ïðîèçâîëüíîå ñëîâî w ∈ R(i, j, k), îíî ÷èòàåòñÿ âäîëüïóòè, êîòîðûé íà÷èíàåòñÿ â qi , íåñêîëüêî ðàç (ìîæåò è 0 ðàç) çàõîäèò â qk èçàêàí÷èâàåòñÿ â qj . Åñëè ýòîò ïóòü íå çàõîäèò â qk , òî âäîëü íåãî ÷èòàåòñÿ ñëîâî èç R(i, j, k − 1), ò. å. w ∈ R(i, j, k − 1). Åñëè æå ýòîò ïóòü çàõîäèò â qk , òîïóñòü u ïîäñëîâî w, êîòîðîå ÷èòàåòñÿ âäîëü ó÷àñòêà ïóòè, íà÷èíàþùåãîñÿâ qi è çàêàí÷èâàþùåãîñÿ â ïåðâîì ïîïàäàíèè â ñîñòîÿíèå qk ; w1 ïîäñëîâîw, êîòîðîå ÷èòàåòñÿ âäîëü ó÷àñòêà, íà÷èíàþùåãîñÿ â ïåðâîì ïîïàäàíèè â qkè çàêàí÷èâàþùåãîñÿ âî âòîðîì ïîïàäàíèè â qk ; .

. . ; ws ïîäñëîâî w, êîòîðîå÷èòàåòñÿ âäîëü ó÷àñòêà, íà÷èíàþùåãîñÿ â ïðåäïîñëåäíåì ïîïàäàíèè â qk è çàêàí÷èâàþùåãîñÿ â ïîñëåäíåì ïîïàäàíèè â qk ; è, íàêîíåö, ïóñòü v ïîäñëîâîw, êîòîðîå ÷èòàåòñÿ âäîëü ó÷àñòêà, íà÷èíàþùåãîñÿ â ïîñëåäíåì ïîïàäàíèè âqk è çàêàí÷èâàþùåãîñÿ â qj .qii -. . .uqk- i -. . .w1qkqk- i -.

. . - i -. . . ......wsqk- i -. . .vqj- iÒîãäà u ∈ R(i, k, k − 1), w1 , . . . , ws ∈ R(k, k, k − 1) è v ∈ R(k, j, k − 1). Îòñþäàñëåäóåò, ÷òî ñëîâî w = uw1 . . . ws v ∈ R(i, k, k − 1)R(k, k, k − 1)∗ R(k, j, k − 1).Îáúåäèíÿÿ îáà ñëó÷àÿ, çàêëþ÷àåì, ÷òî èìååò ìåñòî âêëþ÷åíèå R(i, j, k) ⊆R(i, j, k − 1) ∪ R(i, k, k − 1)R(k, k, k − 1)∗ R(k, j, k − 1). Íåòðóäíî ïðîâåðèòü, ÷òîîáðàòíîå âêëþ÷åíèå òîæå âåðíî. Òàêèì îáðàçîì, ìû äîêàçàëè ðàâåíñòâîR(i, j, k) = R(i, j, k − 1) ∪ R(i, k, k − 1)R(k, k, k − 1)∗ R(k, j, k − 1).Ñëåäîâàòåëüíî, â ñèëó èíäóêöèîííîãî ïðåäïîëîæåíèÿ è çàìêíóòîñòè ðåãóëÿðíûõ ÿçûêîâ îòíîñèòåëüíî îáúåäèíåíèÿ, êîíêàòåíàöèè è çâ¼çäî÷êè Êëèíè îêîí÷àòåëüíî ïîëó÷àåì, ÷òî R(i, j, k) ðåãóëÿðíûé ÿçûê.

×òî è òðåáîâàëîñü äîêàçàòü.Ÿ 9. Ôîðìàëüíûå ãðàììàòèêèŸ 9.29Ôîðìàëüíûå ãðàììàòèêè×àñòî ôîðìàëüíûå ÿçûêè îïèñûâàþòñÿ êàê ñîâîêóïíîñòè ñëîâ, ïîëó÷åííûõ ñ ïîìîùüþ ïðàâèë çàìåíû îäíèõ öåïî÷åê ñèìâîëîâ íà äðóãèå. Òàêîé ïîäõîä ëåæèò â îñíîâåïîíÿòèÿ ôîðìàëüíîé ãðàììàòèêè.  îòëè÷èå îò êîíå÷íûõ àâòîìàòîâ, ôîðìàëüíûåãðàììàòèêè íå ðàñïîçíàþò ñëîâà, à ïîðîæäàþò èõ.

Ëþáóþ ôîðìàëüíóþ ãðàììàòèêó ìîæíî ïðåäñòàâëÿòü êàê íåêîòîðûé ãåíåðàòîð ÿçûêà. Çàïóñê òàêîãî ãåíåðàòîðàïðîèçâîäèòñÿ ñ ïîìîùüþ ¾ñòàðòîâîãî ñèãíàëà¿, ïîñëå ÷åãî íà÷èíàåòñÿ ïîðîæäåíèåñëîâ ÿçûêà. Äåéñòâèÿ ãåíåðàòîðà íà êàæäîì ýòàïå ïîðîæäåíèÿ ñëîâ íåäåòåðìèíèðîâàííû, íî îãðàíè÷åíû êîíå÷íûì ñïèñêîì ïðàâèë. Âðåìÿ îò âðåìåíè ýòîò ïðîöåññïðåðûâàåòñÿ äëÿ òîãî, ÷òîáû âûäàòü î÷åðåäíîå âûõîäíîå ñëîâî. Ìíîæåñòâî âñåõñëîâ, ïîÿâèâøèõñÿ íà âûõîäå â ïðîöåññå ðàáîòû, îáðàçóåò ÿçûê, ïîðîæä¼ííûé äàííîé ãðàììàòèêîé. Ïðîöåññ ïîðîæäåíèÿ ñëîâ ïî ïðàâèëàì ôîðìàëüíîé ãðàììàòèêèáåçóñëîâíî ÿâëÿåòñÿ àëãîðèòìè÷åñêèì.Ðàññìîòðèì àëãîðèòì ïîðîæäåíèÿ ñëîâ ñî ñáàëàíñèðîâàííûìè ñêîáêàìèíàä àëôàâèòîì, ñîñòîÿùåì èç îòêðûâàþùåé ñêîáêè ¾(¿ è çàêðûâàþùåé ñêîáêè ¾)¿.(êðàòêî,ñëîâà) îïðåäåëÿþòñÿ ïî èíäóêöèè:1) Ñëîâî () ñáàëàíñèðîâàííî.2) Åñëè ñëîâî u ñáàëàíñèðîâàííî, òî ñëîâî (u) òîæå ñáàëàíñèðîâàííî.3) Åñëè ñëîâà u è v ñáàëàíñèðîâàííû, òî ñëîâî uv òîæå ñáàëàíñèðîâàííî.Ââåä¼ì âñïîìîãàòåëüíûé ñèìâîë S , êîòîðûì áóäåì îáîçíà÷àòü ëþáîå ñáàëàíñèðîâàííîå ñëîâî.

Àëãîðèòì ìîæíî îïèñàòü ñëåäóþùèìè ïðàâèëàìè:1) Ñëîâî S ìîæíî çàìåíèòü íà ñëîâî ().2) Ñëîâî S ìîæíî çàìåíèòü íà ñëîâî (S).3) Ñëîâî S ìîæíî çàìåíèòü íà ñëîâî SS .Ëþáîå ñáàëàíñèðîâàííîå ñëîâî ïîëó÷àåòñÿ ñ ïîìîùüþ êîíå÷íîãî ÷èñëà ïðèìåíåíèé ïðàâèë 1)3). Ñõåìàòè÷åñêè ïðàâèëà 1)3) ìîæíî ïåðåïèñàòü ñëåäóþùèì îáðàçîì:Ïðèìåð.Ñëîâà ñî ñáàëàíñèðîâàííûìè ñêîáêàìèñáàëàíñèðîâàííûåS −→ ()S −→ (S)S −→ SSÍàïðèìåð, ïðîöåññ ïîðîæäåíèÿ ñëîâà (()()())() ïî äàííûì ïðàâèëàì âûãëÿäèò òàê:S → SS → S() → (S)() → (SS)() → (SSS)() → (()SS)() → (()()S)() → (()()())().Îïðåäåëåíèå.Ôîðìàëüíîé ãðàììàòèêîé íàçûâàåòñÿ óïîðÿäî÷åííàÿ ÷åòâ¼ðêà Γ =hV, T, P, Si, ñîñòîÿùàÿ èç ñëåäóþùèõ îáúåêòîâ:íåòåðìèíàëüíûõ (âñïîìîãàòåëüíûõ) ñèìâîëîâ;á) T êîíå÷íîå ìíîæåñòâî òåðìèíàëüíûõ ñèìâîëîâ òàêîå, ÷òî V ∩ T = ∅;â) P êîíå÷íîå ìíîæåñòâî ïðîäóêöèé, ò. å.

öåïî÷åê âèäà α −→ β , ãäå α, βà) V êîíå÷íîå ìíîæåñòâî(V ∪ T ) , è â α ñîäåðæèòñÿ õîòÿ áû îäèí ýëåìåíò èç V ;∗ã) S íà÷àëüíûé ñèìâîë, S ∈ V .∈30Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêèÏóñòü Γ = hV, T, P, Si ôîðìàëüíàÿ ãðàììàòèêà, α, β ∈ (V ∪ T )∗ .Ãîâîðÿò, ÷òîβαΓ, èïèøóò α −→ β , åñëè ñóùåñòâóþò ñëîâà α0 , α1 , γ , δ òàêèå, ÷òî α = α0 γα1 , β = α0 δα1 ,Îïðåäåëåíèå.ñëîâî íåïîñðåäñòâåííî ïîëó÷àåòñÿ èç ñëîâà â ãðàììàòèêåΓè ïðîäóêöèÿ γ −→ δ ïðèíàäëåæèò ìíîæåñòâó P .ñëîâî âûâîäèìî èç ñëîâà â ãðàììàòèêåÃîâîðÿò, ÷òîβαΓ, è ïèøóòα −→ β , åñëè ñóùåñòâóåò êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ñëîâ β0 , .