1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 6
Текст из файла (страница 6)
÷àñòü, ñîîòâåòñòâóþùàÿ w1 .Ïóñòü âäîëü ó÷àñòêà 2 íà äóãàõ àâòîìàòà ÷èòàåòñÿ ñëîâî α, âäîëüó÷àñòêà 3 ÷èòàåòñÿ ñëîâî β 6= Λ, à âäîëü ó÷àñòêà 4 ÷èòàåòñÿ ñëîâî γ .Íî ìû ìîæåì äâèãàòüñÿ ïî àâòîìàòó òàêæå è ñëåäóþùèì îáðàçîì: ñíà÷àëà ïðîéòè ïåðâóþ è âòîðóþ ÷àñòè ïóòè, çàòåì ïðîéòè k ðàç òðåòüþ÷àñòü ïóòè, à ïîòîì ïðîéòè îñòàâøóþñÿ ÷àñòü. Ïðè ýòîì âäîëü òàêîãîïóòè áóäåò ÷èòàòüñÿ ñëîâî w0 αβ k γw1 , à ïîñêîëüêó ýòîò ïóòü íà÷èíàåòñÿ â íà÷àëüíîì è çàêàí÷èâàåòñÿ â âûäåëåííîì ñîñòîÿíèè, ìû èìååìw0 αβ k γw1 ∈ L. Ëåììà äîêàçàíà.Âîò îäèí èç ïðèìåðîâ ïðèìåíåíèÿ ýòîé ëåììû.
Äîêàæåì, ÷òî ÿçûêL = {am bm | m ∈ N} íå ÿâëÿåòñÿ àâòîìàòíûì. Äåéñòâèòåëüíî, âîçüìåì nêàê â ëåììå î íàêà÷èâàíèè è ðàññìîòðèì êàêîå-íèáóäü ñëîâî am bm ∈ Läëÿ n < m. Ïî ëåììå î íàêà÷èâàíèè, íåêîòîðîå ñëîâî âèäà am+k bm ,k > 0 äîëæíî ñîäåðæàòüñÿ â L. Ïðîòèâîðå÷èå.Çàìåòèì, ÷òî íàïèñàíèå ïðîãðàììû, ðàñïîçíàþùåé âûøåóïîìÿíóòûé ÿçûê L = {am bm | m ∈ N}, íà ëþáîì èç ðàñïðîñòðàíåííûõ àëãîðèòìè÷åñêèõ ÿçûêîâ äîñòàòî÷íî òðèâèàëüíàÿ çàäà÷à.
Ðàññìîòðåííûéïðèìåð ïîêàçûâàåò, ÷òî êîíå÷íûå àâòîìàòû ìîãóò äàëåêî íå âñå.2.3. Ðåãóëÿðíûå ÿçûêè332.3 Ðåãóëÿðíûå ÿçûêèÇäåñü áóäåò äàíî îïðåäåëåíèå ðåãóëÿðíûõ ÿçûêîâ è ïîêàçàíî, ÷òî àâòîìàòíûå ÿçûêè ýòî â òî÷íîñòè ðåãóëÿðíûå ÿçûêè.Îïðåäåëåíèå. Îïðåäåëèì ìíîæåñòâî ðåãóëÿðíûõ âûðàæåíèé íàä êîíå÷íûì àëôàâèòîì A ñëåäóþùèì îáðàçîì:1. ëþáîé ñèìâîë a ∈ A ÿâëÿåòñÿ ðåãóëÿðíûì âûðàæåíèåì;2. ∅, Λ ÿâëÿþòñÿ ðåãóëÿðíûìè âûðàæåíèÿìè;3. åñëè α è β ðåãóëÿðíûå âûðàæåíèÿ, òî (αβ) (α ∪ β) (α∗ ) òîæåÿâëÿþòñÿ ðåãóëÿðíûìè âûðàæåíèÿìè;24. Äðóãèõ ðåãóëÿðíûõ âûðàæåíèé íåò.
Òî åñòü ïðîèçâîëüíàÿ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ ÿâëÿåòñÿ ðåãóëÿðíûì âûðàæåíèåì òîãäà è òîëüêî òîãäà, êîãäà ýòî ìîæåò áûòü óñòàíîâëåíî êîíå÷íûì ÷èñëîì ïðèìåíåíèé ïðåäûäóùèõ ïóíêòîâ äàííîãî îïðåäåëåíèÿ.3Ìû áóäåì îïóñêàòü íåêîòîðûå ñêîáêè â ðåãóëÿðíûõ âûðàæåíèÿõ (âòîì ÷èñëå è âíåøíèå ñêîáêè), êàê ýòî äåëàåòñÿ â îáû÷íîé àëãåáðå, ñ÷èòàÿ, ÷òî îïåðàöèè èìåþò ñëåäóþùèé ïðèîðèòåò: ∗ ñèëüíåå âñåõ, äàëååèäåò ïðèïèñûâàíèå αβ , à ∪ ñàìàÿ ñëàáàÿ ñâÿçêà. Òàê, íàïðèìåð, çàïèñü αβ ∗ ∪ β íà ñàìîì äåëå îçíà÷àåò ((α(β ∗ )) ∪ β).Îïðåäåëèì òåïåðü îòîáðàæåíèå L èç ìíîæåñòâà âñåõ ðåãóëÿðíûõ âûðàæåíèé íàä A â ìíîæåñòâî âñåõ ÿçûêîâ íàä A ñëåäóþùèì îáðàçîì:L(Λ) = {Λ}L(∅) = ∅L(a) = {a}; ( äëÿ âñåõ a ∈ A)L(αβ) = L(α)L(β)L(α ∪ β) = L(α) ∪ L(β)L(α∗ ) = L(α)∗ .Îïðåäåëåíèå.
ßçûê L íàä àëôàâèòîì A íàçûâàåòñÿ ðåãóëÿðíûì, åñëèñóùåñòâóåò ðåãóëÿðíîå âûðàæåíèå α íàä àëôàâèòîì A òàêîå, ÷òî L =L(α).2Ìû3ïðåäïîëàãàåì, ÷òî ñèìâîëû ( è ) íå ïðèíàäëåæàò àëôàâèòó A.Îáðàòèòå âíèìàíèå íà ñïîñîá, êîòîðûì çàäàåòñÿ ïîíÿòèå ðåãóëÿðíîãî âûðàæåíèÿ. Ôàêòè÷åñêè ìû çàäàåì ñïîñîá îáðàçîâàíèÿ âñåõ ðåãóëÿðíûõ âûðàæåíèé, êîòîðûé ïîðîæäàåò íàì âñå íîâûå è íîâûå âûðàæåíèÿ èç óæå èìåþùèõñÿ.
Òàêèå îïðåäåëåíèÿ íàçûâàþòñÿ îïðåäåëåíèÿìè ïî èíäóêöèè.34Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêèÒåîðåìà 2.3.1 Êëàññ àâòîìàòíûõ ÿçûêîâ ñîâïàäàåò ñ êëàññîì ðåãóëÿðíûõ ÿçûêîâ.Äîêàçàòåëüñòâî. Ñíà÷àëà äîêàæåì, ÷òî êàæäûé ðåãóëÿðíûé ÿçûê ÿâ-ëÿåòñÿ àâòîìàòíûì. Ìû äîêàæåì ýòî èíäóêöèåé ïî äëèíå ðåãóëÿðíîãîâûðàæåíèÿ α, çàäàþùåãî ÿçûê.  ñàìîì äåëå, åñëè ýòà äëèíà ðàâíà 1,òî α èìååò îäèí èç ñëåäóþùèõ âèäîâ: a, ∅, Λ, è ÿçûê L(α) èìååò îäèíèç ñëåäóþùèõ âèäîâ: {a}, ∅, {Λ}. Àâòîìàòíîñòü ýòèõ ÿçûêîâ ñëåäóåò èçòåîðåìû 2.2.4.Ïðåäïîëîæèì, òåïåðü, ÷òî äëèíà ðåãóëÿðíîãî âûðàæåíèÿ α áîëüøååäèíèöû, è äëÿ âñåõ ðåãóëÿðíûõ âûðàæåíèé β , äëèíà êîòîðûõ ìåíüøåäëèíû α, óæå äîêàçàíî, ÷òî ÿçûêè L(β) ÿâëÿþòñÿ àâòîìàòíûìè.
Òîãäàâîçìîæíû ñëåäóþùèå ñëó÷àè:Ñëó÷àé 1. α = βγ .Òîãäà L(α) = L(β)L(γ). Ïî èíäóêöèîííîìó ïðåäïîëîæåíèþ ÿçûêèL(β) è L(γ) ÿâëÿþòñÿ àâòîìàòíûìè. Ïî òåîðåìå 2.2.2 ÿçûê L(α) òîæåÿâëÿåòñÿ àâòîìàòíûì.Ñëó÷àé 2. α = β ∪ γ . Ðàññìàòðèâàåòñÿ àíàëîãè÷íî ñëó÷àþ 1.Ñëó÷àé 3. α = β ∗ . Ðàññìàòðèâàåòñÿ àíàëîãè÷íî ñëó÷àþ 1.Äîêàæåì òåïåðü, ÷òî âñÿêèé àâòîìàòíûé ÿçûê ðåãóëÿðåí.Ïóñòü A êîíå÷íûé àâòîìàò è q1 , . . . , qn âñå åãî ñîñòîÿíèÿ. Äëÿêàæäîé òðîéêè i, j, k , 1 6 i, j 6 n, 0 6 k 6 n îïðåäåëèìR(i, j, k) ïî îïðåäåëåíèþ ðàâíî ìíîæåñòâó âñåõ ñëîâ, êîòîðûå ìîæíîïðî÷åñòü âäîëü ïóòåé àâòîìàòà A, èäóùèõ èç ñîñòîÿíèÿ qi â ñîñòîÿíèå qj , êîòîðûå â ïðîìåæóòêå ìåæäó íèìè íå çàõîäÿò íè â îäíîèç ñîñòîÿíèé qk+1 , qk+2 , . . .Çàìåòèì, ÷òî R(i, j, n) áóäåò ìíîæåñòâîì ñëîâ, ïðî÷èòûâàåìûõ âäîëüâñåõ ïóòåé àâòîìàòà A, èäóùèõ èç ñîñòîÿíèÿ qi â ñîñòîÿíèå qj .
Òîãäàî÷åâèäíî, ÷òî åñëè q1 íà÷àëüíîå ñîñòîÿíèå, òî[T (A) =R(1, j, n).qj ∈FÄëÿ äîêàçàòåëüñòâà òåîðåìû äîñòàòî÷íî ïîíÿòü, ÷òî âñå ÿçûêè R(i, j, k),1 6 i, j 6 n, 0 6 k 6 n ðåãóëÿðíû. Äîêàæåì ýòî óòâåðæäåíèå ìåòîäîììàòåìàòè÷åñêîé èíäóêöèè.Ïðè k = 0 ìíîæåñòâî R(i, j, k) ïðåâðàùàåòñÿ â ìíîæåñòâî ñëîâ èçîäíîé áóêâû, ÷èòàåìûõ âäîëü ëþáîé äóãè, èäóùåé èç qi â qj (âîîáùå íåò2.4. Îïðåäåëåíèå ôîðìàëüíûõ ãðàììàòèê35ïðîìåæóòî÷íûõ ñîñòîÿíèé!). Ýòî, î÷åâèäíî, êîíå÷íîå (âîçìîæíî ïóñòîå)ìíîæåñòâî. Åãî ðåãóëÿðíîñòü ëåãêî ñëåäóåò èç îïðåäåëåíèÿ.Ïóñòü óòâåðæäåíèå óæå äîêàçàíî äëÿ k−1. Ðàññìîòðèì ïðîèçâîëüíîåñëîâî èç ìíîæåñòâà R(i, j, k) è ñîîòâåòñòâóþùèé ïóòü â àâòîìàòå, âäîëüêîòîðîãî îíî ÷èòàåòñÿ.
Ýòîò ïóòü íà÷èíàåòñÿ â ñîñòîÿíèè qi , íåñêîëüêîðàç (ìîæåò áûòü è 0 ðàç) çàõîäèò â ñîñòîÿíèå qk è ïîòîì çàêàí÷èâàåòñÿâ ñîñòîÿíèè qj :qi → . . . → qk → . . . → qk → . . . → qk → . . . → qj .Åñëè ýòîò ïóòü âîîáùå íå çàõîäèò â ñîñòîÿíèå qk , òî âäîëü íåãî ÷èòàåòñÿñëîâî èç R(i, j, k − 1). Åñëè ýòîò ïóòü õîòÿ áû ðàç çàõîäèò â ñîñòîÿíèå qk ,òî, â ñèëó òîãî, ÷òî ýòîò ïóòü íå ïðîõîäèò ÷åðåç ñîñòîÿíèÿ ñ íîìåðàìèâûøå k (êðîìå áûòü ìîæåò íà÷àëà qi è êîíöà qj ), âäîëü ó÷àñòêà ïóòèqi → .
. . → qk ïðî÷èòûâàåòñÿ ñëîâî èç 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−1) = L(α),R(i, k, k −1) = L(β), R(k, k, k −1) = L(γ), R(k, j, k − 1) = L(δ), R(i, j, k) =α ∪ βγ ∗ δ , îòêóäà è ñëåäóåò òåîðåìà.¤Òàêèì îáðàçîì, ðåãóëÿðíûå ÿçûêè ýòî â òî÷íîñòè àâòîìàò-íûå ÿçûêè.Óïðàæíåíèå.
∗ Ïóñòü L ðåãóëÿðíûé ÿçûê. Äîêàçàòü, ÷òî ÿçûê L0 ={w0 | w ∈ L}, ãäå w0 îáîçíà÷àåò ñëîâî w, ïåðåïèñàííîå íàîáîðîò, òîæåðåãóëÿðíûé.Óêàçàíèå: ïîêàæèòå, êàê ïî ðåãóëÿðíîìó âûðàæåíèþ äëÿ L ïîñòðîèòü ðåãóëÿðíîåâûðàæåíèå äëÿ L02.4 Îïðåäåëåíèå ôîðìàëüíûõ ãðàììàòèêÌíîãèå ôîðìàëüíûå ÿçûêè ÿâëÿþòñÿ íàáîðîì ñëîâ, ïîëó÷åííûõ ïî îïðåäåëåííûì ïðàâèëàì. Âî ìíîãèõ ñëó÷àÿõ ýòè ïðàâèëà ìîãóò áûòü ïðåäñòàâëåíû â âèäå ôîðìàëüíûõ ãðàììàòèê .36Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêèÐàññìîòðèì ïðèìåð ôîðìàëüíîãî îïðåäåëåíèÿ ïîíÿòèÿ çàïèñü íàòóðàëüíîãî ÷èñëà â àëôàâèòå {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Çàìåòèì, ÷òî êàæäàÿ òàêàÿ çàïèñü åñòü ëèáî 0 ëèáî îäíà èç öèôð 1, 2, 3, 4, 5, 6, 7, 8, 9, ïðèïèñàííàÿ ñëåâà ê íåêîòîðîé ïîñëåäîâàòåëüíîñòè öèôð. Ïîñëåäîâàòåëüíîñòü öèôð, â ñâîþ î÷åðåäü, ýòî ëèáî ïóñòîå ñëîâî Λ ëèáî îäíà èçöèôð 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (0 èñêëþ÷àåì!), ïðèïèñàííàÿ ñëåâà ê ñëîâó,ïðî êîòîðîå óæå èçâåñòíî, ÷òî îíî ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòüþ öèôð.Ñõåìàòè÷åñêè ýòî ìîæíî çàïèñàòü òàê:hçàïèñü íàò. ÷èñëàihçàïèñü íàò. ÷èñëàihçàïèñü íàò. ÷èñëài···hçàïèñü íàò. ÷èñëài→ 0→ 1 hïîñë-òü íàò.÷èñåëi→ 2 hïîñë-òü íàò.÷èñåëihïîñë-òü íàò.÷èñåëihïîñë-òü íàò.÷èñåëihïîñë-òü íàò.÷èñåëi···hïîñë-òü íàò.÷èñåëi→ Λ→ 0 hïîñë-òü íàò.÷èñåëi→ 1 hïîñë-òü íàò.÷èñåëi→ 9 hïîñë-òü íàò.÷èñåëi(2.1)→ 9 hïîñë-òü íàò.÷èñåëi .Çàïèñè òàêîãî âèäà íàçûâàþòñÿ ïðîäóêöèÿìè4 .
Çàïèñü hçàïèñü íàò. ÷èñëài,ðàññìàòðèâàåìàÿ, êàê åäèíûé ñèìâîë, ÿâëÿåòñÿ â äàííîì ñëó÷àå íåêîòîðûì îáùèì ãðàììàòè÷åñêèì ïîíÿòèåì (ãðàììàòè÷åñêîé êàòåãîðèåé).Ñòðåëêó → â ýòèõ çàïèñÿõ ìîæíî ïîíèìàòü, êàê ñî÷åòàíèå ñëîâ â ÷àñòíîì ñëó÷àå ìîæåò áûòü ñëîâîì âèäà. Ïîëüçóÿñü ýòèìè çàïèñÿìè, ìûìîæåì ïðîñëåäèòü, íàïðèìåð, ïðîèñõîæäåíèå äåñÿòè÷íîé çàïèñè 308:hçàïèñü íàò. ÷èñëài → 3 hïîñë-òü íàò.÷èñåëi →→ 30 hïîñë-òü íàò.÷èñåëi →→ 308 hïîñë-òü íàò.÷èñåëi →→ 308 (= 308Λ).Ýòà ïîñëåäîâàòåëüíîñòü ïðèìåíåíèÿ ïðîäóêöèé ïîêàçûâàåò, ÷òî 308 ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì ãðàììàòè÷åñêîãî ïîíÿòèÿ hçàïèñü íàò. ÷èñëài.Ìîæíî çàïèñàòü â ïîäîáíîì âèäå è ïîíÿòèå àðèôìåòè÷åñêîãî âûðàæåíèÿ îò ïåðåìåííûõ x, y (ïðè ýòîì ê àëôàâèòó áóäóò äîáàâëåíû íîâûåñèìâîëû (, ), +, −, ×, / ).
Çàïèñè â âèäå ïðîäóêöèé, êîòîðûå ìû ïðèâåäåì íèæå, ìîæíî ïîíèìàòü êàê ñëåäóþùóþ ôðàçó:4îò àíãëèéñêîãî produce - ïðîèçâîäèòü2.4. Îïðåäåëåíèå ôîðìàëüíûõ ãðàììàòèê37Ëþáàÿ çàïèñü íàòóðàëüíîãî ÷èñëà ÿâëÿåòñÿ àðèôìåòè÷åñêèìâûðàæåíèåì, ïåðåìåííûå x è y ÿâëÿþòñÿ àðèôìåòè÷åñêèìè âûðàæåíèÿìè, à òàêæå åñëè èçâåñòíî, ÷òî äâà ñëîâà vè w ÿâëÿþòñÿ àðèôìåòè÷åñêèìè âûðàæåíèÿìè, òî è ñëîâà(v + w), (v − w), (v × w), (v/w), òàêæå áóäóò àðèôìåòè÷åñêèìè âûðàæåíèÿìè.Èòàê, çàïèøåì ïîíÿòèå àðèôìåòè÷åñêîãî âûðàæåíèÿ â âèäå ïðîäóêöèé:hàðèôì.âûðàæ-åihàðèôì.âûðàæ-åihàðèôì.âûðàæ-åihàðèôì.âûðàæ-åihàðèôì.âûðàæ-åihàðèôì.âûðàæ-åihàðèôì.âûðàæ-åi→→→→→→→hçàïèñü íàò.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
