1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 8
Текст из файла (страница 8)
Ïîëó÷èì íåêîòîðûé (âîîáùå ãîâîðÿ, íåäåòåðìèíèðîâàííûé)00àâòîìàò A . Îí ðàñïîçíà¼ò íåêîòîðûé àâòîìàòíûé ÿçûê L(A ). Îïðåäåëèì òåïåðü ãîìîìîðôèçìθçàäàíèåì åãî çíà÷åíèé íà ñèìâîëàõ èçäóþùèì îáðàçîì: êàæäîìó ñèìâîëóáûëà ïîìå÷åíà äóãà àâòîìàòàA,a ∈ AA ñëå-ñîïîñòàâèì ñëîâî, êîòîðûìäëÿ êîòîðîé áûë ïðåäíàçíà÷åí äàííûéñèìâîë. Íåòðóäíî óáåäèòüñÿ, ÷òî ÿçûê, ðàñïîçíàâàåìûé àâòîìàòîì A,L(A0 ) îòíîñèòåëüíî ãîìîìîðôèçìà θ, è ïîýòîìóÿâëÿåòñÿ îáðàçîì ÿçûêàîí òîæå àâòîìàòåí.2.9Îïòèìèçàöèÿ àâòîìàòîâÈñïîëíåíèå àëãîðèòìîâ è èõ îïèñàíèå òðåáóþò âñåãäà îïðåäåë¼ííûõ çàòðàò.
Ýòè çàòðàòû ìîãóò âûðàæàòüñÿ â çàòðà÷åííûõ äåíüãàõ, âðåìåíè,îïåðàòèâíîé ïàìÿòè êîìïüþòåðà è ò.ï. Âïðî÷åì, êàê ïðàâèëî, îíè òàêèëè èíà÷å ñâîäÿòñÿ ê äåíüãàì. Ïîýòîìó çàäà÷è îïòèìèçàöèè çàòðàò íàèñïîëüçîâàíèå ÷åãî áû òî íè áûëî âñåãäà âîëíóþò ÷åëîâåêà äî ñàìîéãëóáèíû äóøè.Çäåñü ìû çàéì¼ìñÿ îïòèìèçàöèåé êîíå÷íûõ àâòîìàòîâ, à èìåííî, áóäóò ðàññìîòðåíû íåêîòîðûå ñïîñîáû, ïîçâîëÿþùèå óìåíüøèòü ÷èñëî ñî-Ãëàâà 2. Àâòîìàòíûå ÿçûêè50ñòîÿíèé êîíå÷íîãî àâòîìàòà ïðè ñîõðàíåíèè ðàñïîçíàâàåìîãî èì ÿçûêà, è äàæå íàéòè ñàìûé ïðîñòîé àâòîìàò, ðàñïîçíàþùèé äàííûé ÿçûê.Óäèâèòåëüíûì ôàêòîì îêàæåòñÿ òî, ÷òî àâòîìàò ñ íàèìåíüøèì ÷èñëîìñîñòîÿíèé, ðàñïîçíàþùèé äàííûé ÿçûê, â íåêîòîðîì ñìûñëå ÿâëÿåòñÿåäèíñòâåííûì: ëþáûå äâà òàêèå àâòîìàòà îêàæóòñÿ èçîìîðôíûìè.
Åñëè êîíå÷íûé àâòîìàò, ðàñïîçíàþùèé íåêîòîðûé ÿçûê, íåîáõîäèìî ðåàëèçîâàòü â âèäå êîìïüþòåðíîé ïðîãðàììû, òî ýòè ìåòîäû ïîçâîëÿò íàìíàïèñàòü íàèáîëåå ïðîñòóþ òàêóþ ïðîãðàììó è äàæå áóäóò ãàðàíòèðîâàòü, ÷òî áîëåå ïðîñòóþ ïðîãðàììó íàïèñàòü íåâîçìîæíî.Ñíà÷àëà ðàññìîòðèì äâà ïðîñòåéøèõ ñïîñîáà, ïîçâîëÿþùèå óìåíüøèòü ÷èñëî ñîñòîÿíèé àâòîìàòà áåç èçìåíåíèÿ ÿçûêà, ðàñïîçíàâàåìîãîèì. Ýòèõ ñïîñîáîâ, âîîáùå ãîâîðÿ, íåäîñòàòî÷íî äëÿ ïîñòðîåíèÿ ñàìûõîïòèìàëüíûõ àâòîìàòîâ, íî, òåì íå ìåíåå, ïîëüçà îò íèõ î÷åâèäíà.Ïåðâûé èç íèõ îñíîâàí íà ïîíÿòèè äîñòèæèìîñòè, à âòîðîé íà ïîíÿòèè êîäîñòèæèìîñòè.Ñîñòîÿíèå s íåäåòåðìèíèðîâàííîãî àâòîìàòà hS, A, s0 , t, F iíàçûâàåòñÿ äîñòèæèìûì, åñëè â íåãî ñóùåñòâóåò ïóòü ïî ñòðåëêàì,íà÷èíàþùèéñÿ â íåêîòîðîì íà÷àëüíîì ñîñòîÿíèè.
 ïðîòèâíîì ñëó÷àåñîñòîÿíèå íàçûâàåòñÿ íåäîñòèæèìûì. Àâòîìàò íàçûâàåòñÿ äîñòèæèìûì, âñå åãî ñîñòîÿíèÿ äîñòèæèìû.Îïðåäåëåíèå 2.9.1Äëÿ êàæäîãî íåäåòåðìèíèðîâàííîãî àâòîìàòà A îïðåäåëèì àâòîìàòAa , ïîëó÷àþùèéñÿ èç A óäàëåíèåì âñåõ íåäîñòèæèìûõ ñîñòîÿíèé è ñòðåëîê, âõîäÿùèõ èëè âûõîäÿùèõ èç íèõ. Ïîñêîëüêó ìû ðàññìàòðèâàåì äåòåðìèíèðîâàííûå àâòîìàòû êàê ÷àñòíûå ñëó÷àè íåäåòåðìèíèðîâàííûõ,ýòà æå îïåðàöèÿ ïðèìåíèìà è ê äåòåðìèíèðîâàííûì àâòîìàòàì.Çàìåòèì, ÷òî åñëè àâòîìàòòîìàòAaAÿâëÿåòñÿ äåòåðìèíèðîâàííûì, òî è àâ-òàêæå ÿâëÿåòñÿ äåòåðìèíèðîâàííûì.Ïîñêîëüêó íåäîñòèæèìûå ñîñòîÿíèÿ íå ó÷àñòâóþò â ðàñïîçíàâàíèèñëîâ, ñëåäóþùåå ïðåäëîæåíèå î÷åâèäíî:Äëÿ ëþáîãî íåäåòåðìèíèðîâàííîãî àâòîìàòà A,àâòîìàò Aa äîñòèæèì è L(Aa ) = L(A).Ïðåäëîæåíèå 2.9.1Ñîñòîÿíèå íåäåòåðìèíèðîâàííîãî àâòîìàòà íàçûâàåòñÿ êîäîñòèæèìûì èç íåãî ñóùåñòâóåò ïóòü â íåêîòîðîå çàêëþ÷èòåëüíîå ñîñòîÿíèå.
Àâòîìàò íàçûâàåòñÿ êîäîñòèæèìûì, åñëèâñå åãî ñîñòîÿíèÿ êîäîñòèæèìû.Îïðåäåëåíèå 2.9.22.9. Îïòèìèçàöèÿ àâòîìàòîâ51Äëÿ êàæäîãî íåäåòåðìèíèðîâàííîãî àâòîìàòàìèíèðîâàííûé àâòîìàòAcAîïðåäåëèì íåäåòåð-êàê ðåçóëüòàò óäàëåíèÿ èçAâñåõ ñîñòîÿíèé,íå ÿâëÿþùèõñÿ êîäîñòèæèìûìè, à òàêæå ñòðåëîê, âõîäÿùèõ èëè âûõîäÿùèõ èç íèõ.Çàìåòèì, ÷òî åñëèA äåòåðìèíèðîðâàííûé àâòîìàò, òî àâòîìàòAcóæå íå îáÿçàòåëüíî áóäåò äåòåðìèíèðîâàííûì. ×èòàòåëþ ïðåäëàãàåòñÿñàìîñòîÿòåëüíî ïðèäóìàòü ñîîòâåòñòâóþùèé ïðèìåð àâòîìàòà.Äëÿ ëþáîãî íåäåòåðìèíèðîâàííîãî àâòîìàòà A,àâòîìàò Ac êîäîñòèæèì è L(Ac ) = L(A).Ïðåäëîæåíèå 2.9.2Äîêàçàòåëüñòâî.
Ïîñêîëüêó àâòîìàòìû èìååìAcÿâëÿåòñÿ ÷àñòüþ àâòîìàòàA,L(Ac ) ⊆ L(A). Ñ äðóãîé ñòîðîíû, åñëè â àâòîìàòå A ñóùåñòâóåòïóòü èç íåêîòîðîãî íà÷àëüíîãî ñîñòîÿíèÿ â çàêëþ÷èòåëüíîå ñîñòîÿíèå,âäîëü êîòîðîãî ÷èòàåòñÿ ñëîâîïóòü ïðîõîäèò, ïîïàäàþò ââAc .Ac ,w,òî âñå ñîñòîÿíèÿ, ÷åðåç êîòîðûå ýòîòè, ñòàëî áûòü, ýòîò æå ïóòü âîçìîæåí èÎòñþäà ñëåäóåò è îáðàòíîå âêëþ÷åíèåL(A) ⊆ L(Ac ). Ñëåäóþùåå ïðåäëîæåíèå ïðîâåðÿåòñÿ íåïîñðåäñòâåííî.Äëÿ ëþáîãî íåäåòåðìèíèðîâàííîãî àâòîìàòà A,àâòîìàòû (Aa )c è (Ac )a ñîâïàäàþò, è ïîëó÷àþòñÿ èç A óäàëåíèåì âñåõñîñòîÿíèé, êîòîðûå íå äîñòèæèìû èëè íå êîäîñòèæèìû.Ïðåäëîæåíèå 2.9.3Îòñþäà ëåãêî ñëåäóåòÄëÿ ëþáîãî íåäåòåðìèíèðîâàííîãî àâòîìàòà Aóñëîâèå L(A) = ∅ ýêâèâàëåíòíî òîìó, ÷òî (Aa )c ïóñòîé àâòîìàò.Ïðåäëîæåíèå 2.9.4Òåïåðü ìû çàéì¼ìñÿ ïîñòðîåíèåì îïòèìàëüíûõ àâòîìàòîâ.Àâòîìàò A íàçûâàåòñÿ ìèíèìàëüíûì, åñëè ÷èñëî ñîñòîÿíèé ëþáîãî àâòîìàòà, ðàñïîçíàþùåãî ÿçûê L(A), áîëüøå ëèáîðàâíî ÷èñëó ñîñòîÿíèé àâòîìàòà A.Îïðåäåëåíèå 2.9.3Íàì ïîíàäîáèòñÿÏóñòü A êîíå÷íûé àâòîìàò íàä àëôàâèòîì Añî ìíîæåñòâîì çàêëþ÷èòåëüíûõ ñîñòîÿíèé F .
Åãî ñîñòîÿíèÿ s è t íàçîâ¼ì íåðàçëè÷èìûìè, åñëè äëÿ ëþáîãî w ∈ A∗ ñïðàâåäëèâà ýêâèâàëåíòíîñòü s · w ∈ F ⇔ t · w ∈ F . Ìû áóäåì çàïèñûâàòü íåðàçëè÷èìîñòü s èt êàê s ∼ t.Îïðåäåëåíèå 2.9.4Ãëàâà 2. Àâòîìàòíûå ÿçûêè52Äîêàçàòåëüñòâî ñëåäóþùåãî óòâåðæäåíèÿ íå ñîñòàâëÿåò áîëüøîãî òðóäà.Îòíîøåíèå íåðàçëè÷èìîñòè íà ìíîæåñòâå ñîñòîÿíèé êîíå÷íîãî àâòîìàòà ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè,ò.å., îíî ðåôëåêñèâíî, ñèììåòðè÷íî è òðàíçèòèâíî.Ïðåäëîæåíèå 2.9.5Êîíå÷íûé àâòîìàò íàçûâàåòñÿ ðåäóöèðîâàííûì,åñëè îòíîøåíèå ∼ íà í¼ì ñîâïàäàåò ñ ðàâåíñòâîì, ò.å., äëÿ ëþáûõñîñòîÿíèé x è y x ∼ y ýêâèâàëåíòíî x = y .Îïðåäåëåíèå 2.9.5Òåîðåìà 2.9.1 Äëÿ ëþáîãî êîíå÷íîãî àâòîìàòà A ñóùåñòâóåò ðåäóöèðîâàííûé àâòîìàò Ar , ñî ñëåäóþùèìè ñâîéñòâàìè:1.
L(Ar ) = L(A)2. Åñëè A äîñòèæèìûé àâòîìàò, òî è Ar äîñòèæèìûé àâòîìàò.Äîêàçàòåëüñòâî òåîðåìû. ÏóñòüàâòîìàòhSr , Ar , ir , tr , Fr i,SrArirtr (s/∼ , a)Fr=====A = hS, A, i, t, F i.ÎïðåäåëèìArêàêâ êîòîðîìS/∼ (ôàêòîðìíîæåñòâî S ïî ∼),A,i/∼ (êëàññ ýêâèâàëåíòíîñòè i ïî ∼),t(s, a)/∼ , äëÿ âñåõ s ∈ S , a ∈ Ar (= A),{s/∼ | s ∈ F }.Ýòî îïðåäåëåíèå íóæäàåòñÿ â ïðîâåðêå êîððåêòíîñòè, à èìåííî, íåîá-tr (s/∼ , a) íå çàâèñèò îò âûáîðà êîíêðåòíîãî ïðåäñòàâèòåëÿ â êëàññå s/∼ . Âîçüì¼ì ïðîèçâîëüíûå s, q òàêèå,÷òî s ∼ q , è ïðîâåðèì, ÷òî t(s, a) ∼ t(q, a), äëÿ âñåõ a ∈ A. Ïóñòüw ∈ A∗ . Èìååì: t(s, a) · w = s · aw ∈ F ⇔ q · aw ∈ F.
Ó÷èòûâàÿ, ÷òîq·aw = t(q, a)·w, ïîëó÷èì ýêâèâàëåíòíîñòü t(s, a)·w ∈ F ⇔ t(q, a)·w ∈ F ,îòêóäà t(s, a) ∼ t(q, a).õîäèìî óáåäèòüñÿ, ÷òî çíà÷åíèå2.9. Îïòèìèçàöèÿ àâòîìàòîâ53Êðîìå ýòîãî, íàì ïîíàäîáèòñÿ åù¼ îäíî ñâîéñòâî:åñëè s ∼ q , òî s ∈ F ⇔ q ∈ F ,∼ ïðè w = Λ.Fr ñîñòîèò èç ýëåìåíòîâ ìíîF âõîäèò â íåêîòîðûé ýëåìåíòêîòîðîå íåïîñðåäñòâåííî ïîëó÷àåòñÿ èç îïðåäåëåíèÿ äëÿÈç íåãî ñëåäóåò, ÷òî êàæäûé ýëåìåíò èçæåñòâàèçF,è êàæäûé ýëåìåíò ìíîæåñòâàFr .Ñíà÷àëà ïîêàæåì, ÷òîs/∼ èFr ⇔(s/∼ ) · w ∈ FrAr ðåäóöèðîâàííûé àâòîìàò.
Ïóñòüq/∼ íåðàçëè÷èìû, ò.å., òàêîâû, ÷òî äëÿ âñåõ w ∈ A∗ (s/∼ ) · w ∈(q/∼ ) · w ∈ Fr . Ââèäó äîêàçàííîãî ðàíåå, óòâåðæäåíèåýêâèâàëåíòíî s · w ∈ F , à óòâåðæäåíèå (q/∼ ) · w ∈ Fr ýêâèâàëåíòíîq · w ∈ F . Îòñþäà ìû ïîëó÷èì îïðåäåëåíèå äëÿ s ∼ q : äëÿ ëþáîãî w ∈ A∗âûïîëíåíî s · w ∈ F ⇔ q · w ∈ F . Îòñþäà ïîëó÷èì, ÷òî s/∼ = q/∼ , ò.å.,îòíîøåíèå íåðàçëè÷èìîñòè íà Ar ñîâïàäàåò ñ ðàâåíñòâîì.Ïðîâåðèì ñîâïàäåíèå ÿçûêîâ L(Ar ) è L(A). Äåéñòâèòåëüíî,w ∈ L(Ar ) ⇔ ir · w ∈ Fr ⇔(i/∼ ) · w ∈ Fr ⇔(i · w)/∼ ∈ Fr ⇔i·w ∈F ⇔w ∈ L(A).Îñòàëîñü ïðîâåðèòü, ÷òî äîñòèæèìîñòü A âëå÷¼ò äîñòèæèìîñòü Ar .
Ïóñòüs ∈ S . Ïîêàæåì, ÷òî íàéä¼òñÿ w ∈ A∗ òàêîå, ÷òî ir · w = s/∼ . Òàê êàê A∗äîñòèæèì, íàéäåòñÿ ñëîâî w ∈ A òàêîå, ÷òî i · w = s. Îòñþäà ïîëó÷èìir · w = (i/∼ ) · w = (i · w)/∼ = s/∼ ,÷òî è òðåáîâàëîñü.Ôàêòè÷åñêè â äîêàçàííîé òåîðåìå îïèñàíà îïåðàöèÿA 7→ Ar ,ïîçâî-ëÿþùàÿ ïî ëþáîìó àâòîìàòó ñòðîèòü ðåäóöèðîâàííûé àâòîìàò, ðàñïîçíàþùèé òîò æå ñàìûé ÿçûê.Ñëåäóþùåå óòâåðæäåíèå äà¼ò ïî êðàéíåé ìåðå îäèí ýôôåêòèâíûéñïîñîá îïðåäåëåíèÿ ïî äâóì ñîñòîÿíèÿì àâòîìàòà, ÿâëÿþòñÿ ëè îíè íåðàçëè÷èìûìè, ñâîäÿ ïðîâåðêó óñëîâèÿ íåðàçëè÷èìîñòè ê ïåðåáîðó êîíå÷íîãî ñåìåéñòâà ñëîâ.
Îòñþäà ìû ïîëó÷èì àëãîðèòì, ïîçâîëÿþùèé ïîA ýôôåêòèâíî ñòðîèòü äîñòèæèìûé è ðåäóöèðîâàí(Aa )r , ðàñïîçíàþùèé òîò æå ñàìûé ÿçûê. Êàê áóäåò âèäíîëþáîìó àâòîìàòóíûé àâòîìàòèç äàëüíåéøåãî, îí æå áóäåò è ìèíèìàëüíûì àâòîìàòîì.Ãëàâà 2. Àâòîìàòíûå ÿçûêè54Ïóñòü A = hS, A, i, t, F i êîíå÷íûé àâòîìàò èn ÷èñëî åãî ñîñòîÿíèé. Òîãäà åãî ñîñòîÿíèÿ s è t íåðàçëè÷èìû òîãäàè òîëüêî òîãäà, êîãäà äëÿ âñåõ ñëîâ w íàä àëôàâèòîì ýòîãî àâòîìàòà,äëèíà êîòîðûõ ìåíåå, ÷åì n2 âûïîëíåíî s · w ∈ F ⇔ t · w ∈ F .Ïðåäëîæåíèå 2.9.6Äîêàçàòåëüñòâî.  ñàìîì äåëå, åñëè äëÿ íåêîòîðîãî ñëîâàs·w ∈F ⇔t·w ∈Fwóñëîâèå(2.4)22íå âûïîëíåíî, è |w| > n , òî ñðåäè êàê ìèíèìóì (n + 1) ïàð ñîñòîÿíèé000âèäà hs · w , t · w i, ãäå w íà÷àëüíûé ñåãìåíò w , îáÿçàòåëüíî âñòðåòÿòñÿw äîïóñêàåò ïðåäñòàâëåíèå â âèäå w =w0 w1 w2 , w1 6= Λ òàêîå, ÷òî s · w0 = s · w0 w1 è t · w0 = t · w0 w1 .
Òîãäà èç ýòèõðàâåíñòâ ïîëó÷èì s·w0 w2 = s·w0 w1 w2 = s·w è t·w0 w2 = t·w0 w1 w2 = t·w .äâå îäèíàêîâûå ïàðû, ò.å., ñëîâîÎòñþäà ïîëó÷èì, ÷òî ýêâèâàëåíòíîñòü (2.4) íàðóøàåòñÿ óæå íà ñëîâåw0 w2 ,Èòàê, ìû âûÿñíèëè, ÷òî, åñëè w , êîòîðîå2è t, èìååò äëèíó êàê ìèíèìóì n , òî ìîæíî íàéòè è ñëîâîêîòîðîå êîðî÷å, ÷åìðàçëè÷àåòsw.ìåíüøåé äëèíû ñ òåì æå ñâîéñòâîì. Îòñþäà è ñëåäóåò óòâåðæäåíèå.Ïóñòü Ai = hSi , A, si , ti , Fi i, i = 0, 1 êîíå÷íûåàâòîìàòû íàä îäíèì è òåì æå àëôàâèòîì A. Íàçîâ¼ì îòîáðàæåíèåϕ : S0 → S1 èçîìîðôèçìîì èç àâòîìàòà A0 íà àâòîìàò A1 , åñëè ϕâçàèìíî îäíîçíà÷íî, ϕ(s0 ) = s1 , ϕ(F0 ) = F1 , è äëÿ ëþáûõ s ∈ S è a ∈A âûïîëíåíî ϕ(t0 (s, a)) = t1 (ϕ(s), a). Àâòîìàòû A0 è A1 íàçûâàþòñÿèçîìîðôíûìè, åñëè ñóùåñòâóåò èçîìîðôèçì èç A0 íà A1 .
Ýòîò ôàêòîáîçíà÷àåòñÿ êàê A0 ∼= A1 .Îïðåäåëåíèå 2.9.6Èçîìîðôíîñòü àâòîìàòîâ ôàêòè÷åñêè îçíà÷àåò, ÷òî ýòè àâòîìàòûîäèíàêîâû ñ òî÷íîñòüþ äî ïåðåîáîçíà÷åíèÿ ñîñòîÿíèé.2Î÷åâèäíî, ÷òî ðåäóöèðîâàííîñòü è äîñòèæèìîñòü àâòîìàòà ñîõðàíÿþòñÿ ïðè èçîìîðôèçìå, ò.å. åñëè äâà àâòîìàòà èçîìîðôíû, è îäèí èç íèõðåäóöèðîâàí, òî è âòîðîé òîæå; àíàëîãè÷íî è äëÿ ñâîéñòâà äîñòèæèìîñòè.1. Àâòîìàò ÿâëÿåòñÿ ìèíèìàëüíûì òîãäà è òîëüêî òîãäà, êîãäà îí ðåäóöèðîâàí è äîñòèæèì.Òåîðåìà 2.9.22 Åñëèðàññìàòðèâàòü àâòîìàòûhS, s, F, `a ia∈A ,ãäå`a (u) = t(u, a),hS, A, s, t, F iêàê àëãåáðàè÷åñêèå ñèñòåìû âèäàòî ïîíÿòèå èçîìîðôèçìà àâòîìàòîâ ïðåîáðàçóåòñÿâ îáû÷íîå ïîíÿòèå èçîìîðôèçìà àëãåáðàè÷åñêèõ ñèñòåì.2.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
