1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 9
Текст из файла (страница 9)
Îïòèìèçàöèÿ àâòîìàòîâ552. Ëþáûå äâà ìèíèìàëüíûõ àâòîìàòà, ðàñïîçíàþùèå îäèí è òîòæå ÿçûê, èçîìîðôíû ìåæäó ñîáîé.Äîêàçàòåëüñòâî. Äîêàæåì ï. 1. Î÷åâèäíî, ÷òî âñÿêèé ìèíèìàëüíûéàâòîìàòAðåäóöèðîâàí è äîñòèæèì, ïîñêîëüêó â ïðîòèâíîì ñëó÷àå êàêìèíèìóì îäèí èç àâòîìàòîâ÷åìAa , Aráóäåò èìåòü åù¼ ìåíüøå ñîñòîÿíèé,A.AÏóñòü òåïåðü àâòîìàòâîëüíûé àâòîìàòB,ðåäóöèðîâàí è äîñòèæèì. Âîçüìåì ïðîèç-ðàñïîçíàþùèé ÿçûêL(A)è èìåþùèé íàèìåíüøååâîçìîæíîå ÷èñëî ñîñòîÿíèé. Êîíå÷íî æå, îí áóäåò äîñòèæèì è ðåäóöèðîâàí. Åñëè ìû äîêàæåì, ÷òîA∼= B, òî òåì ñàìûì ìû äîêàæåì òåîðåìó.Íà ñàìîì äåëå ýòî áóäåò ñëåäîâàòü èç ñëåäóþùåé ëåììû:Ëþáûå äâà äîñòèæèìûõ è ðåäóöèðîâàííûõ àâòîìàòà,ðàñïîçíàþùèõ îäèí è òîò æå ÿçûê, èçîìîðôíû.Ëåììà 2.9.1Äîêàçàòåëüñòâî ëåììû.Ai = hSi , A, qi , ti , Fi i, i = 0, 1 äîñòèæèìûå è ðåäóöèðîâàííûå àâòîìàòû, îáëàäàþùèå ñâîéñòâîì L(A0 ) = L(A1 ).∗Îïðåäåëèì îòîáðàæåíèå ϕ : S0 → S1 êàê ϕ(q0 ·w) = q1 ·w , äëÿ âñåõ w ∈ AÏóñòüè ïîêàæåì, ÷òî îíî ÿâëÿåòñÿ òðåáóåìûì èçîìîðôèçìîì.
Ýòî îïðåäåëåíèå íóæäàåòñÿ â ïðîâåðêå êîððåêòíîñòè, à èìåííî, íàì íóæíî ïðîâåðèòü,ϕ(q0 · w) íå çàâèñèò îò ïðåäñòàâëåíèÿ ýëåìåíòà èç S0 â âèäåq0 · w, è ÷òî ϕ îïðåäåëåíî íà âñ¼ì ìíîæåñòâå S0 .∗Ïðåäïîëîæèì, ÷òî u, v ∈ A è q0 · u = q0 · v . Îòñþäà ñëåäóåò, ÷òî÷òî çíà÷åíèå∀w ∈ A∗ (q0 · uw = q0 · vw).Ñëåäîâàòåëüíî,∀w ∈ A∗ (q0 · uw ∈ F0 ⇔ q0 · vw ∈ F0 ).Äàëåå, îòñþäà ïîëó÷èì∀w ∈ A∗ (uw ∈ L(A0 ) ⇔ vw ∈ L(A0 )).ÏîñêîëüêóL(A0 ) = L(A1 ),áóäåò âûïîëíåíî òàêæå è∀w (uw ∈ L(A1 ) ⇔ vw ∈ L(A1 )).Îòñþäà ïîëó÷èì∀w (q1 · uw ∈ F1 ⇔ q1 · vw ∈ F1 ),Ãëàâà 2. Àâòîìàòíûå ÿçûêè56q1 ·u è q1 ·v íåðàçëè÷èìû. Èç ðåäóöèðîâàííîñòè A1 ñëåäóåò,÷òî q1 · u = q1 · v .Îòîáðàæåíèå ϕ îïðåäåëåíî íà âñ¼ì ìíîæåñòâå S0 , ïîñêîëüêó â ñèëóäîñòèæèìîñòè àâòîìàòà A0 , ëþáîé ýëåìåíò èç S0 ïðåäñòàâèì â âèäå q0 ·w ,∗äëÿ ïîäõîäÿùåãî w ∈ A .Òåïåðü îñòàëîñü ïðîâåðèòü, ÷òî ϕ ÿâëÿåòñÿ èçîìîðôèçìîì, ò.å., ÷òîîíî èíúåêòèâíî, ñþðúåêòèâíî, îáëàäàåò ñâîéñòâîì ϕ(t(s, a)) = t1 (ϕ(s), a),äëÿ âñåõ s ∈ S0 , a ∈ A, ñîõðàíÿåò íà÷àëüíîå ñîñòîÿíèå, ò.å., ϕ(q0 ) = q1 ,à òàêæå ñîõðàíÿåò âûäåëåííûå ñîñòîÿíèÿ, ò.å., óñëîâèå s ∈ F0 âñåãäàýêâèâàëåíòíî ϕ(s) ∈ F1 .Ñþðúåêòèâíîñòü ϕ ñëåäóåò èç òîãî, ÷òî ââèäó äîñòèæèìîñòè A1 , ëþáîé ýëåìåíò èç S1 ïðåäñòàâèì â âèäå q1 ·w , äëÿ ïîäõîäÿùåãî w , è ïîýòîìóϕ(q0 · w) = q1 · w.Èíúåêòèâíîñòü ϕ äîêàçûâàåòñÿ àíàëîãè÷íî äîêàçàòåëüñòâó êîððåêòíîñòè îïðåäåëåíèÿ ϕ, à èìåííî, íóæíî äîêàçàòü, ÷òî èç q1 · u = q1 · vñëåäóåò q0 · u = q0 · v .
Ñîîòâåòñòâóþùåå äîêàçàòåëüñòâî ìîæíî ïîëó÷èòüò.å., ñîñòîÿíèÿèç äîêàçàòåëüñòâà êîððåêòíîñòè ïðîñòîé ñìåíîé èíäåêñîâ.∗Äàëåå, ïóñòü s = q0 · w , w ∈ A , a ∈ A. Òîãäàϕ(t0 (s, a)) = ϕ(t0 (q0 · w, a)) = ϕ(q0 · wa) = q1 · wa = t1 (q1 · w, a) = t1 (ϕ(s), a),÷òî è òðåáîâàëîñü.Ñâîéñòâîϕ(q0 ) = q1âûïîëíåíî, ïîñêîëüêóϕ(q0 ) = ϕ(q0 · Λ) = q1 · Λ =q1 .Óñëîâèå ñîõðàíåíèÿ âûäåëåííûõ ñîñòîÿíèé îòîáðàæåíèåì ϕ ìîæíî∀w ∈ A∗ (q0 · w ∈ F0 ⇔ q1 · w ∈ F1 ), ÷òî, â ñâîþ î÷åðåäü,∗ýêâèâàëåíòíî ∀w ∈ A (w ∈ L(A0 ) ⇔ w ∈ L(A1 )), ò.å., ðàâåíñòâó ÿçûêîâçàïèñàòü òàê:L(A0 ) è L(A1 ). Òàêèì îáðàçîì, è ýòî ñâîéñòâî âûïîëíåíî, è ϕ èçîìîðôèçì àâòîìàòîâ.Ëåììà äîêàçàíà.Äîêàæåì ï.
2. Ïîñêîëüêó, êàê óæå âûÿñíèëîñü, ìèíèìàëüíûå àâòîìàòû, ðàñïîçíàþùèå îäèí è òîò æå ÿçûê, ÿâëÿþòñÿ äîñòèæèìûìè èðåäóöèðîâàííûìè àâòîìàòàìè, ðàñïîçíàþùèìè îäèí è òîò æå ÿçûê, îíèèçîìîðôíû.Òàêèì îáðàçîì, ìèíèìàëüíûé àâòîìàò êàê áû ÿâëÿåòñÿ óäîñòîâåðåíèåì ëè÷íîñòè ðàñïîçíàâàåìîãî èì àâòîìàòíîãî ÿçûêà: îí îäíîçíà÷íî2.9.
Îïòèìèçàöèÿ àâòîìàòîâ57îïðåäåëÿåòñÿ ïî ýòîìó ÿçûêó, è ÿçûêè ñîâïàäàþò òîãäà è òîëüêî òîãäà,êîãäà ýòè àâòîìàòû îäèíàêîâû (èçîìîðôíû).Ïîêàæåì íà ïðèìåðå, êàê ìîæíî óïðîñòèòü àâòîìàò, ïîëüçóÿñü îïèñàííûìè çäåñü ìåòîäàìè áåç èçìåíåíèÿ ÿçûêà.Ðàññìîòðèì ñëåäóþùèé àâòîìàòDDEDEDEEDDDEEDEDEEDEDEDEÍåäîñòèæèìûìè ñîñòîÿíèÿìè åãî ÿâëÿþòñÿ ñîñòîÿíèÿ 4, 8 è 12. Ïîñëåèõ óäàëåíèÿ âìåñòå ñ âõîäÿùèìè èëè âûõîäÿùèìè èç íèõ ñòðåëêàìè ìûïîëó÷èì óæå äîñòèæèìûé àâòîìàòDEDDEEDDEEDEDEDEDEÒåïåðü íåïîñðåäñòâåííî óáåæäàåìñÿ, ÷òî êëàññàìè îòíîøåíèÿ íåðàçëè÷èìîñòè ÿâëÿþòñÿ ñëåäóþùèå ìíîæåñòâà ñîñòîÿíèé:{2, 5}, {1},ïðè÷¼ì ñîñòîÿíèå{7, 10, 11}{7, 10, 11}, {3, 6, 9},ÿâëÿåòñÿ âûäåëåííûì.Ðåçóëüòàòîì ðåäóöèðîâàíèÿ òàêîãî àâòîìàòà áóäåò ñëåäóþùèé àâòîìàò:DE^`DE^`DE^`Îí æå è áóäåò ìèíèìàëüíûì.DE^`Ãëàâà 2.
Àâòîìàòíûå ÿçûêè582.10ÏóñòüÒåîðåìà ÌàéõèëëàÍåðîóäàL ïðîèçâîëüíûé ÿçûê íàä àëôàâèòîì∗îòíîøåíèå ≈L íà A ñëåäóþùèì îáðàçîì:A.Îïðåäåëèì áèíàðíîåx ≈L y ⇔ ∀w ∈ A∗ (xw ∈ L ↔ yw ∈ L).Íåòðóäíî âèäåòü, ÷òî≈Lðåôëåêñèâíî, ñèììåòðè÷íî è òðàíçèòèâíî,ò.å., ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè.Ïóñòü L ïðîèçâîëüíûé ÿçûê íàä àëôàâèòîì A. Òîãäà ñëåäóþùèå óñëîâèÿ ýêâèâàëåíòíû:Òåîðåìà 2.10.11. L àâòîìàòíûé ÿçûê2.
÷èñëî êëàññîâ ýêâèâàëåíòíîñòè ≈L êîíå÷íî.Äîêàçàòåëüñòâî. ÏóñòüL àâòîìàòíûé ÿçûê, è ïóñòüA äîñòè-æèìûé êîíå÷íûé àâòîìàò, ðàñïîçíàþùèé ýòîò ÿçûê. Äëÿ êàæäîãî åãîçàôèêñèðóåì íåêîòîðîå ñëîâî γ(s) òàêîå, ÷òî s = i · γ(s)∗è ïîêàæåì, ÷òî êàæäîå ñëîâî w ∈ A ýêâèâàëåíòíî íåêîòîðîìó ñëîâóñîñòîÿíèÿâèäàsγ(s).Òåì ñàìûì áóäåò äîêàçàíà êîíå÷íîñòü ÷èñëà êëàññîâ ýêâèâà∗ëåíòíîñòè ≈L .  ñàìîì äåëå, ïðîâåðèì, ÷òî ïðîèçâîëüíîå ñëîâî α ∈ A∗ýêâèâàëåíòíî ñëîâó γ(i · α). Äëÿ ïðîèçâîëüíîãî w ∈ A èìååì:αw ∈ L ⇔ i · (αw) ∈ F ⇔ (i · α) · w ∈ F ⇔⇔ (i · γ(i · α)) · w ∈ F ⇔ i · (γ(i · α)w) ∈ F ⇔ γ(i · α)w ∈ L,îòêóäà è ñëåäóåò óòâåðæäåíèå à âìåñòå ñ íåé è êîíå÷íîñòü ÷èñëà êëàññîâäëÿ≈L .Çàìåòèì äëÿ áóäóùåãî, ÷òî òåì ñàìûì ìû òàêæå äîêàçàëè, ÷òî ÷èñëî êëàññîâ ýêâèâàëåíòíîñòèàâòîìàòà, ðàñïîçíàþùåãî≈LL.íå ïðåâîñõîäèò ÷èñëà ñîñòîÿíèé ëþáîãîÏîçæå ìû äîêàæåì, ÷òî îíî ðàâíî ÷èñëóñîñòîÿíèé ìèíèìàëüíîãî àâòîìàòà, ðàñïîçíàþùåãîÏðåäïîëîæèì òåïåðü, ÷òî ÷èñëî êëàññîâ≈LL.êîíå÷íî.
Ïîñòðîèì íåêî-òîðûé êîíå÷íûé àâòîìàò, êîòîðûé áóäåò ðàñïîçíàâàòü ÿçûêåãî àëôàâèòîì áóäåò ìíîæåñòâîêëàññû ýêâèâàëåíòíîñòè ïî≈L .A.Ïóñòüα ≈L β , òî α ∈ Lβ ∈ L (äîñòàòî÷íî â îïðåäåw = Λ). Ïîñëå ýòîãî çàìå÷àíèÿ ìûÇàìåòèì, ÷òî åñëèâûïîëíåíî òîãäà è òîëüêî òîãäà, êîãäàëåíèè ýòîé ýêâèâàëåíòíîñòè âçÿòüL.Ñîñòîÿíèÿìè ýòîãî àâòîìàòà áóäóò2.10. Òåîðåìà ÌàéõèëëàÍåðîóäà59ìîæåì îïðåäåëèòü ìíîæåñòâî âûäåëåííûõ ñîñòîÿíèéFêàê ìíîæåñòâîL.
Äàëåå, îïðåäåëèì ôóíêöèþt(u/≈L , a) = ua/≈L . Ýòî îïðåäåëå-êëàññîâ, ñîñòîÿùèõ èç ýëåìåíòîâ ÿçûêàïåðåõîäîâtñëåäóþùèì ðàâåíñòâîì:íèå íóæäàåòñÿ â ïðîâåðêå íà êîððåêòíîñü, à èìåííî, íóæíî ïðîâåðèòü,00÷òî èç u/≈L = u /≈L ñëåäóåò, ÷òî ua/≈L = u a/≈L . Äåéñòâèòåëüíî, ïóñòü∗w ∈ A . Òîãäà(ua)w ∈ L ⇔ u(aw) ∈ L ⇔ u0 (aw) ∈ L ⇔ (u0 a)w ∈ L.Îòñþäà ïîëó÷èì òðåáóåìîåòîìàòà îïðåäåëèì, êàêua ≈L u0 a.Íà÷àëüíîå ñîñòîÿíèå íàøåãî àâ-Λ/≈L .Òåïåðü îñòàëîñü ïðîâåðèòü, ÷òîw ∈Lýêâèâàëåíòíîw ∈ L(A).Ýòîñëåäóåò èç ñëåäóþùåé ýêâèâàëåíòíîñòè:w ∈ L ⇔ Λ/≈L · w = w/≈L ⊆ L ⇔ w/≈L ∈ F.Çàìåòèì, ÷òî ÷èñëî ñîñòîÿíèé ïîñòðîåííîãî íàìè â äîêàçàòåëüñòâåýòîé òåîðåìû àâòîìàòà ñîâïàäàåò ñ ÷èñëîì êëàññîâ ýêâèâàëåíòíîñòè≈L .Ïîñêîëüêó, êàê óæå îòìå÷àëîñü, ÷èñëî ýòèõ êëàññîâ íå ïðåâîñõîäèò ÷èñëàñîñòîÿíèé ëþáîãî àâòîìàòà, ðàñïîçíàþùåãîL,ïîñòðîåííûé íàìè àâòî-ìàò ÿâëÿåòñÿ ìèíèìàëüíûì.Åñëè L àâòîìàòíûé ÿçûê, òî ÷èñëî ñîñòîÿíèéðàñïîçíàþùåãî åãî ìèíèìàëüíîãî àâòîìàòà ðàâíî ÷èñëó êëàññîâ ýêâèâàëåíòíîñòè îòíîøåíèÿ ≈L .Ñëåäñòâèå 2.10.1Ïîêàæåì, êàê ïðèìåíèòü êðèòåðèé, ïðåäîñòàâëÿåìûé òåîðåìîé 2.10.1L = {ap | p ïðîñòîå}.
Äëÿäëÿ äîêàçàòåëüñòâà íåàâòîìàòíîñòè ÿçûêàíà÷àëà âñïîìíèì äâà õîðîøî èçâåñòíûõ ôàêòà. Ïåðâûé ñîñòîèò â òîì,÷òî ïðîñòûõ ÷èñåë áåñêîíå÷íî ìíîãî. Âòîðîé ôàêò ñîñòîèò â òîì, ÷òî âíàòóðàëüíûõ ÷èñëàõ ñóùåñòâóþò ñêîëü óãîäíî äëèííûå èíòåðâàëû áåçïðîñòûõ ÷èñåë (äåéñòâèòåëüíî, ïðè n > 2 ñðåäè ÷èñåë âèäà n! + k , k =2, . . . , n íåò ïðîñòûõ ÷èñåë). Äîêàæåì, ÷òî ëþáûå äâà ñëîâà ak è al , k < líå ÿâëÿþòñÿ íåðàçëè÷èìûìè. Äëÿ ýòîãî, ïîëüçóÿñü óïîìÿíóòûìè âûøåñâîéñòâàìè âûáåðåì ïðîèçâîëüíîå ïðîñòîå ÷èñëî p òàêîå, ÷òî p + (lp−kkk p−kíå ïðîñòîå.
Ïîëîæèì m = p − k è w = a. Òîãäà a w = a a= apal w = al ap−k = ap+(l−k) ∈/ L. Îòñþäà ïîëó÷èì, ÷òî ak è al , k <íåðàçëè÷èìû.− k)∈ L,l íå60Ãëàâà 2. Àâòîìàòíûå ÿçûêèÃëàâà 3Àâòîìàòíûå ñòðóêòóðûÈçó÷åíèþ àëãåáðàè÷åñêèõ ñòðóêòóð, ò.å., ìíîæåñòâ ñ çàäàííûìè íà íèõîòíîøåíèÿìè è îïåðàöèÿìè, ïîñâÿùåíî ìíîãî ñîâðåìåííûõ ïóáëèêàöèé.Àáñòðàêòíîå ïîíÿòèå àëãåáðàè÷åñêîé ñòðóêòóðû (óïîòðåáëÿþòñÿ òàêæåòàêèå ñèíîíèìû, êàê ¾ñòðóêòóðà¿, ¾ìîäåëü¿, ¾àëãåáðàè÷åñêàÿ ñèñòåìà¿),êîòîðîå ñîâñåì åù¼ íåäàâíî, â 80å ãîäû ïðîøëîãî âåêà áûëî èçâåñòíî ëèøü óçêîìó êðóãó ñïåöèàëèñòîâ äàæå â ñðåäå ïðîôåññèîíàëüíûõìàòåìàòèêîâ, âîçíèêøåå èç å¼ âíóòðåííèõ íóæä, ñåãîäíÿ ñòàëî îáùåèçâåñòíûì è äàæå ïåðåøàãíóëî ðàìêè ÷èñòîé ìàòåìàòèêè, ïðî÷íî îáîñíîâàâøèñü â òåîðåòè÷åñêîì è ïðàêòè÷åñêîì ïðîãðàììèðîâàíèè.
Îñîáîåìåñòî çäåñü çàíèìàåò èçó÷åíèå ñòðóêòóð, êîòîðûå â ïðèíöèïå äîïóñêàþòðåàëèçàöèþ íà êîìïüþòåðå, òàê íàçûâàåìûõ êîíñòðóêòèâíûõ àëãåáðàè÷åñêèõ ñèñòåì. Èõ ýëåìåíòû ìîæíî ïðåäñòàâëÿòü ýëåìåíòàìè êîìïüþòåðíûõ òèïîâ äàííûõ, òàêèìè, êàê, íàïðèìåð ÷èñëà, ñòðîêè, ìàòðèöû èò.ï., ïðîâîäèòü íàä íèìè âû÷èñëåíèÿ, îïðåäåëÿòü èñòèííîñòü èëè ëîæíîñòü îòíîøåíèé íà ýëåìåíòàõ. Òàêèå ñòðóêòóðû ìîæíî, â ÷àñòíîñòè,ðåàëèçîâûâàòü íà êîìïüþòåðå â âèäå àáñòðàêòíûõ òèïîâ äàííûõ.Çäåñü ìû ðàññìîòðèì ÷àñòíûé, íî âàæíûé ñëó÷àé, êîãäà ñòðóêòóðàäîïóñêàåò ðåàëèçàöèþ íà êîìïüþòåðå ñ ïîìîùüþ àëãîðèòìîâ, çàäàâàåìûõ êîíå÷íûìè àâòîìàòàìè.
Òàêèå ñòðóêòóðû ìû íàçîâ¼ì àâòîìàòíûìè. Òî÷íîå îïðåäåëåíèå áóäåò äàíî ïîçæå. Ñ îäíîé ñòîðîíû, ââèäó îãðàíè÷åííîñòè èñïîëüçóåìûõ çäåñü àëãîðèòìîâ, êîòîðûå ìîãóò çàäàâàòüñÿëèøü àâòîìàòàìè, äàëåêî íå âñå åñòåñòâåííûå ñòðóêòóðû ìîãóò áûòüïðåäñòàâëåíû ñ ïîìîùüþ àâòîìàòîâ. Îäíàêî, ñ äðóãîé ñòîðîíû, îêàçûâàåòñÿ, ÷òî ñòðóêòóðû, çàäàâàåìûå àâòîìàòàìè, èìåþò î÷åíü ñèëüíûåàëãîðèòìè÷åñêèå ñâîéñòâà, è îá ýòî áóäóò ñâèäåòåëüñòâîâàòü íåêîòîðûå61Ãëàâà 3.
Àâòîìàòíûå ñòðóêòóðû62ïðèâåä¼ííûå çäåñü ðåçóëüòàòû.3.1Êîíâîëþöèè è îïðåäåëåíèå àâòîìàòíûõìîäåëåéÏðåæäå, ÷åì ïðèâåñòè îïðåäåëåíèå àâòîìàòíîé ñòðóêòóðû, ââåä¼ì íåêîòîðûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ.Íàì ïîíàäîáèòñÿ íåêîòîðûé ñïîñîá ïðåäñòàâëåíèÿnîêñëîâ, ñëîâàýëåìåíòû êîòîðûõ ìîãóò èìåòü ðàçëè÷íûå äëèíû, â âèäå ñëîâ íàä íåêîòîðûì àëôàâèòîì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
