С.С. Марченков - Избранные главы дискретной математики (1124120), страница 10
Текст из файла (страница 10)
. . bjn â àëôàâèòå B ñîãëàñíîñëåäóþùåìó ïðàâèëó. Ïîëàãàåì bj1 = g(ai1 , q1 ). Íàõîäèì çíà÷åíèå qs1 =f (ai1 , q1 ). Òîãäà bj2 = g(ai2 , qs2 ). Äàëåå âû÷èñëÿåì çíà÷åíèå f (ai2 , qs1 ).Âîîáùå, åñëè óæå íàéäåíî, ÷òî qsl = f (ail , qsl−1 ), òî ïîëàãàåì bjl+1 =g(ail+1 , qsl ) è íàõîäèì çíà÷åíèå qsl+1 = f (ail+1 , qsl ).Ïî îïðåäåëåíèþ ñ÷èòàåì, ÷òî ïóñòîå ñëîâî àâòîìàò A ïåðåâîäèò òàêæå â ïóñòîå ñëîâî. Òåì ñàìûì àâòîìàò A çàäàåò îòîáðàæåíèå ìíîæåñòâàA∗ â ìíîæåñòâî B ∗ , êîòîðîå ìû áóäåì íàçûâàòü, ðåàëèçóåìîé (âû÷èñëèìîé) àâòîìàòîì A. Äëÿ óïðîùåíèÿ çàïèñè ýòó ôóíêöèþ áóäåì îáîçíà÷àòü òåì æå ñèìâîëîì A.Èç îïèñàíèÿ âû÷èñëåíèÿ ôóíêöèè A ëåãêî óñìîòðåòü, ÷òî ñ ââåäåíèåì ïàðàìåòðà t (¾âðåìÿ¿) ýòó ôóíêöèþ ìîæíî ïðåäñòàâèòü ñ ïîìîùüþñëåäóþùèõ:ôóíêöèåé âûõîäîâêîíå÷íî-àâòîìàòíîéôóíêöèåéêàíîíè÷åñêèõ óðàâíåíèé y(t) = f (x(t), q(t − 1)),q(t) = g(x(t), q(t − 1)),q(0) = q1 ,44ãäå ÷åðåç y(t) îáîçíà÷åí âûõîäíîé ñèìâîë àâòîìàòà A â ìîìåíò âðåìåíè t.Òàê æå, êàê äëÿ àâòîìàòà áåç âûõîäà, àâòîìàò A è ðåàëèçóåìóþ èìêîíå÷íî-àâòîìàòíóþ ôóíêöèþ ìîæíî çàäàòü ñ ïîìîùüþ äèàãðàììû Ìóðà.
Åäèíñòâåííîå îòëè÷èå äëÿ àâòîìàòîâ ñ âûõîäîì ñîñòîèò â òîì, ÷òîíà äóãå äèàãðàììû Ìóðà, âåäóùåé èç ñîñòîÿíèÿ qj â ñîñòîÿíèå ql è ïîìå÷åííîé áóêâîé ai (ò.å. ïðè âûïîëíåíèè óñëîâèÿ f (ai , qj ) = ql ), âñëåä çàáóêâîé ai ÷åðåç çàïÿòóþ ñòàâèòñÿ áóêâà bp = g(ai , qj ). Íèæå íà ðèñóíêåèçîáðàæåí ïðèìåð äèàãðàììû Ìóðà äëÿ àâòîìàòà ñ âõîäíûì àëôàâèòîìA = {a1 , a2 } è âûõîäíûì àëôàâèòîì B = {b1 , b2 }.a1 , b2a2 , b1 ∗q1a2 , b1q2a1 , b1q3a1 , b2a2 , b2Äëÿ àâòîìàòîâ ñ âûõîäîì îäíîé èç öåíòðàëüíûõ çàäà÷ ÿâëÿåòñÿ ïðîáëåìààâòîìàòîâ.
Íàçîâåì äâà àâòîìàòà ñ âûõîäîì, åñëè ñîâïàäàþò ôóíêöèè, ðåàëèçóåìûå ýòèìè àâòîìàòàìè. Ïóñòü A = (A, B, Q, f, g, q1 ) àâòîìàò ñ âûõîäîì, qj , ql ñîñòîÿíèÿ àâòîìàòà A. Áóäåì ãîâîðèòü, ÷òî ñîñòîÿíèÿ qj , ql(âàâòîìàòå A), åñëè ýêâèâàëåíòíû àâòîìàòûýêâèâàëåíòíîñòèýêâèâàëåíòíûìèýêâèâàëåíòíûAj = (A, B, Q, f, g, qj ),Al = (A, B, Q, f, g, ql ).îòëè÷èìûìèÍåýêâèâàëåíòíûå ñîñòîÿíèÿ íàçûâàåì òàêæåñîñòîÿíèÿìè.Åñëè ñîñòîÿíèÿ qj , ql îòëè÷èìû â àâòîìàòå A, òî ñóùåñòâóåò òàêîå ñëîâîā â àëôàâèòå A, ÷òî Aj (ā) 6= Al (ā).
 ýòîì ñëó÷àå ãîâîðÿò, ÷òî ñëîâî āñîñòîÿíèÿ qj , ql â àâòîìàòå A. òåîðåìå 3.1 äàåòñÿ íåóëó÷øàåìàÿ âåðõíÿÿ îöåíêà äëÿ äëèíû ñëîâà,îòëè÷àþùåãî â àâòîìàòå ñ r ñîñòîÿíèÿìè äâà îòëè÷èìûõ ñîñòîÿíèÿ.îòëè÷àåòÅñëè â àâòîìàòå ñ r > 2 ñîñòîÿíèÿìè äâàñîñòîÿíèÿ îòëè÷èìû, òî îíè îòëè÷èìû ñëîâîì äëèíû, íå ïðåâîñõîäÿùåé r − 1.Òåîðåìà 3.1(Ý.
Ìóð).Ïóñòü A = (A, B, Q, f, g, q1 ) àâòîìàò ñ âûõîäîì, èìåþùèé r ñîñòîÿíèé. Äëÿ ëþáîãî n > 0 îïðåäåëèì íà ìíîæåñòâåQ îòíîøåíèå ýêâèâàëåíòíîñòè εn : ñîñòîÿíèÿ qj , ql ∈ Q ñ÷èòàåì ýêâèâàëåíòíûìè â ñìûñëå îòíîøåíèÿ εn â òîì è òîëüêî òîì ñëó÷àå, êîãäàqj , ql íåîòëè÷èìû â àâòîìàòå A ñëîâàìè äëèíû n (î÷åâèäíî, ÷òî òàêæåÄîêàçàòåëüñòâî.45è ñëîâàìè ìåíüøåé äëèíû). Ñëîâîì äëèíû 0 (ò.å. ïóñòûì ñëîâîì) áóäóò íåîòëè÷èìû ëþáûå ñîñòîÿíèÿ èç Q. Èíà÷å ãîâîðÿ, ε0 ýòîîòíîøåíèå ýêâèâàëåíòíîñòè íà Q (âñå ñîñòîÿíèÿ èç Q ýêâèâàëåíòíû âñìûñëå îòíîøåíèÿ ε0 ).Ïðè ïåðåõîäå îò îòíîøåíèÿ εn ê îòíîøåíèþ εn+1 ñîñòîÿíèÿ, íåýêâèâàëåíòíûå â ñìûñëå εn , áóäóò, êîíå÷íî, íåýêâèâàëåíòíû è â ñìûñëåîòíîøåíèÿ εn+1 . Ïóñòü qj , ql ñîñòîÿíèÿ, ýêâèâàëåíòíûå â ñìûñëå îòíîøåíèÿ εn , íî îòëè÷èìûå â àâòîìàòå A.
Ïðåäïîëîæèì, ÷òî ñëîâî ai1 . . . aipîòëè÷àåò ñîñòîÿíèÿ qj , ql â àâòîìàòå A. Áóäåì òàêæå ñ÷èòàòü, ÷òî äëèíàp âûáðàíà íàèìåíüøåé âîçìîæíîé (ò.å. ñëîâàìè äëèíû p − 1 ñîñòîÿíèÿqj , ql îòëè÷èòü íåâîçìîæíî). Ïîíÿòíî, ÷òî p > n + 1. Îáîçíà÷èì ÷åðåçqu , qv ñîñòîÿíèÿ, â êîòîðûå ïåðåõîäÿò àâòîìàòû Aj , Al ïîä äåéñòâèåìñëîâà ai1 . . . aip−n−1 . Òîãäà ñîñòîÿíèÿ qu , qv îòëè÷èìû ñëîâîì aip−n . .
. aipäëèíû n + 1, íî íåîòëè÷èìû ñëîâàìè äëèíû n (èíà÷å ñîñòîÿíèÿ qj , ql áûëè áû îòëè÷èìû ñëîâàìè äëèíû p − 1, ÷òî íåâîçìîæíî ïî âûáîðó ÷èñëàp). Èíà÷å ãîàîðÿ, ñîñòîÿíèÿ qu , qv ýêâèâàëåíòíû â ñìûñëå îòíîøåíèÿ εn ,íî íå ýêâèâàëåíòíû â ñìûñëå îòíîøåíèÿ εn+1 .Èòàê, åñëè êàêîå-ëèáî ìíîæåñòâî ñîñòîÿíèé, ýêâèâàëåíòíûõ â ñìûñëåîòíîøåíèÿ εn , ñîäåðæèò îòëè÷èìûå ñîñòîÿíèÿ, òî ïðè ïåðåõîäå ê îòíîøåíèþ εn+1 õîòÿ áû îäíî èç òàêèõ ìíîæåñòâ ðàçáèâàåòñÿ íà äâà èëèáîëåå ïîäìíîæåñòâ, ýêâèâàëåíòíûõ â ñìûñëå îòíîøåíèÿ εn+1 . Ïîñêîëüêóäëÿ îòíîøåíèÿ ε0 ýòî ìíîæåñòâî îäíî, à âñåãî ÷èñëî òàêèõ ìíîæåñòâ íåïðåâîñõîäèò r, ïîëó÷àåì, ÷òî ïîñëå îòíîøåíèÿ εr−1 äàëüíåéøåãî ¾äðîáëåíèÿ¿ îòíîøåíèé ýêâèâàëåíòíîñòè çàâåäîìî íå ïðîèñõîäèò.
Äðóãèìèñëîâàìè, ëþáûå îòëè÷èìûå â àâòîìàòå A ñîñòîÿíèÿ îòëè÷èìû ñëîâîìäëèíû, íå ïðåâîñõîäÿùåé r − 1. Òåîðåìà äîêàçàíà.ïîëíîåÊàê âèäíî èç ïðèâîäèìîãî íèæå ïðèìåðà, âåðõíÿÿ îöåíêà, óêàçàííàÿâ òåîðåìå 3.1, â îáùåì ñëó÷àå íå ìîæåò áûòü ïîíèæåíà.0, 11q10100q201q3...0...1001qr−1010qrÑîñòîÿíèÿ qr−1 , qr â ýòîì ïðèìåðå îòëè÷èìû ñëîâîì 1r−1 , íî íå îòëè÷èìûíèêàêèì ñëîâîì ìåíüøåé äëèíû (âûõîäíîé ñèìâîë àâòîìàòà íå çàâèñèòîò âõîäà è óêàçàí âíóòðè ñîîòâåòñòâóþùåãî êðóæêà).Èòàê, åñëè àâòîìàò A èìååò r ñîñòîÿíèé, òî, êàê âûòåêàåò èç äîêàçàííîé òåîðåìû, äëÿ ïðîâåðêè îòëè÷èìîñòè ïðîèçâîëüíûõ äâóõ ñîñòîÿíèé46qj , ql àâòîìàòà A äîñòàòî÷íî ïîäàòü íà âõîä àâòîìàòîâ Aj , Al âñå ñëîâà āäëèíû, íå ïðåâîñõîäÿùåé r − 1, è ñðàâíèòü ïîëó÷àþùèåñÿ ïðè ýòîì âûõîäû Aj (ā) è Al (ā). Ðàçóìååòñÿ, èñïîëüçîâàíèå çäåñü àâòîìàòîâ Aj , Alâìåñòî àâòîìàòà A íå áîëåå ÷åì ïåðåôîðìóëèðîâàíèå çàäà÷è â óäîáíûõ òåðìèíàõ.
Íà ñàìîì äåëå àâòîìàò A ¾ïðèâîäèòñÿ¿ â ñîñòîÿíèå qj(èëè ñîñòîÿíèå ql ), à çàòåì íà âõîä àâòîìàòà ïîäàþòñÿ âñå ñëîâà ā óêàçàííîé äëèíû. Ñòîèò åùå îòìåòèòü, ÷òî, êàê ïîêàçûâàåò ïðèâåäåííûéâûøå ïðèìåð àâòîìàòà ñ âûõîäîì, áåç äîïîëíèòåëüíîé èíôîðìàöèè îáàâòîìàòå (ïîìèìî èíôîðìàöèè î ÷èñëå ñîñòîÿíèé àâòîìàòà) óìåíüøèòü÷èñëî ñëîâ, ïîäàâàåìûõ íà âõîä àâòîìàòà, íåëüçÿ.Íà îñíîâå òåîðåìû 3.1 ìîæíî ðåøèòü âîïðîñ îá ýêâèâàëåíòíîñòè äâóõàâòîìàòîâ. Èìåííî, ïóñòü èçâåñòíî, ÷òî àâòîìàòûA = (A, B, Q, f, g, q1 ),A0 = (A, B, Q0 , f 0 , g 0 , q10 )èìåþò ñîîòâåòñòâåííî r è r0 ñîñòîÿíèé. Ñ÷èòàåì, ÷òî ìíîæåñòâà Q èQ0 íå èìåþò îáùèõ ýëåìåíòîâ.
Äëÿ ïðîâåðêè ýêâèâàëåíòíîñòè àâòîìàòîâ A, A0 îáðàçóåì ôîðìàëüíîå îáúåäèíåíèå A ∪ A0 àâòîìàòîâ A è A0 .Èìåííî, ìíîæåñòâîì ñîñòîÿíèé ýòîãî îáúåäèíåíèÿ îáúÿâèì ìíîæåñòâîQ ∪ Q0 . Ôóíêöèè ïåðåõîäîâ è âûõîäîâ áóäóò ¾ñîñòàâëåíû¿ èç ôóíêöèéf, g è f 0 , g 0 , äåéñòâóþùèå êàæäàÿ íà ñâîåì ìíîæåñòâå A × Q èëè A0 × Q0 .Âûáîð íà÷àëüíîãî ñîñòîÿíèÿ â àâòîìàòå A ∪ A0 ðîëè íå èãðàåò. Òîãäàîòëè÷èìîñòü ñîñòîÿíèé q1 , q10 â àâòîìàòå A ∪ A0 ðàâíîñèëüíà íåýêâèâàëåíòíîñòè àâòîìàòîâ A, A0 .
Ñîãëàñíî òåîðåìå 3.1, äëÿ âûÿñíåíèÿ îòëè÷èìîñòè ñîñòîÿíèé q1 , q10 äîñòàòî÷íî ðàññìîòðåòü âñå ñëîâà äëèíû, íåïðåâîñõîäÿùåé r + r0 − 1. Åñëè òåïåðü âåðíóòüñÿ ê èñõîäíûì àâòîìàòàìA è A0 , òî ïîëó÷èì, ÷òî äëÿ ïðîâåðêè ýêâèâàëåíòíîñòè àâòîìàòîâ A, A0äîñòàòî÷íî ïîäàòü íà èõ âõîäû âñå ñëîâà ā äëèíû, íå ïðåâîñõîäÿùåér + r0 − 1, è ñðàâíèòü ïîëó÷àþùèåñÿ ïðè ýòîì âûõîäû A(ā) è A0 (ā).ÓÏÐÀÆÍÅÍÈßÏîñòðîèòü àâòîìàò ñ âõîäíûì è âûõîäíûì àëôàâèòîì {0, 1}, êîòîðûé ïåðåâîäèò ñëîâà äëèíû 1 è 2 ñîîòâåòñòâåííî â ñëîâà 0 è 00, à âñÿêîåñëîâî ai1 . .
. ain , ãäå n > 3, â ñëîâî 00ai1 . . . ain−2 .1.47 2. Îñòàòî÷íûå ôóíêöèè. Âåñ ôóíêöèè ãëàâå 2 ìû ââåëè ïîíÿòèÿ ïðàâîèíâàðèàíòíîé ýêâèâàëåíòíîñòè è ðåãóëÿðíîãî ìíîæåñòâà, ÷òî ïîçâîëèëî äàòü îïèñàíèå êîíå÷íî-àâòîìàòíûõìíîæåñòâ, íå îïèðàþùååñÿ íà ïîíÿòèå àâòîìàòà. Íå÷òî ïîäîáíîå ìûáû õîòåëè ïîëó÷èòü äëÿ êîíå÷íî-àâòîìàòíûõ ôóíêöèé. Äëÿ ýòîãî íàìïîòðåáóåòñÿ ââåñòè ïîíÿòèÿ äåòåðìèíèðîâàííîé ôóíêöèè è îñòàòî÷íîéôóíêöèè.Ïóñòü A, B êîíå÷íûå àëôàâèòû, ϕ ôóíêöèÿ, îòîáðàæàþùàÿ ìíîæåñòâî A∗ â ìíîæåñòâî B ∗ . Íàçîâåì ôóíêöèþ ϕ,åñëè äëÿ ëþáûõ ñëîâ ā, b̄ â àëôàâèòå A ñëîâî ϕ(ā) ÿâëÿåòñÿ íà÷àëîìñëîâà ϕ(āb̄) è, êðîìå òîãî, |ϕ(ā)| = |ā|, ãäå |ā| åñòü äëèíà ñëîâà ā.
Èíûìèñëîâàìè, ôóíêöèÿ ϕ äåòåðìèíèðîâàííà, åñëè îíà ñîõðàíÿåò äëèíó ñëîâàè äëÿ ëþáîãî ā ∈ A∗ äëèíû n i-ÿ (1 6 i 6 n) áóêâà ñëîâà ϕ(ā) çàâèñèòòîëüêî îò ïåðâûõ i áóêâ ñëîâà ā.Ñâîéñòâî äåòåðìèíèðîâàííîñòè ëåãêî óñòàíàâëèâàåòñÿ äëÿ êîíå÷íîàâòîìàòíûõ ôóíêöèé.
 ñàìîì äåëå, ïóñòü ôóíêöèÿ ϕ ðåàëèçóåòñÿ àâòîìàòîì A = (A, B, Q, f, g, q1 ). Òîãäà ïðè ïîäà÷å íà âõîä àâòîìàòà A ñëîâàāb̄ (áóêâû ñëîâà āb̄ ïîäàþòñÿ íà âõîä àâòîìàòà A ñëåâà íàïðàâî, íà÷èíàÿñ ïåðâîé áóêâû ñëîâà ā) àâòîìàò A ñíà÷àëà ïåðåðàáàòûâàåò ñëîâî ā âñëîâî ϕ(ā), à çàòåì ñëîâî b̄ â îñòàâøóþñÿ ÷àñòü ñëîâà ϕ(āb̄). Òàêèì îáðàçîì, ϕ(ā) åñòü íà÷àëî ñëîâà ϕ(āb̄). Ñâîéñòâî ñîõðàíåíèÿ äëèíû ñëîâàî÷åâèäíî.Äëÿ äåòåðìèíèðîâàííîé ôóíêöèè ϕ ââåäåì ïîíÿòèå.
Ïóñòü ā ïðîèçâîëüíîå ñëîâî â àëôàâèòå A. Ñîãëàñíî îïðåäåëåíèþäåòåðìèíèðîâàííîñòè äëÿ âñÿêîãî ñëîâà b̄ â àëôàâèòå A ñëîâî ϕ(ā) åñòüíà÷àëî ñëîâà ϕ(āb̄). Ñëåäîâàòåëüíî, ìîæíî ñëåäóþùèì îáðàçîì îïðåäåëèòüϕā , îòîáðàæàþùóþ A∗ â B ∗ : çíà÷åíèåì ϕā (b̄)ïóñòü áóäåò òî (åäèíñòâåííîå) ñëîâî, êîíêàòåíàöèÿ êîòîðîãî ñî ñëîâîìϕ(ā) äàåò ñëîâî ϕ(āb̄). Èíà÷å ãîâîðÿ, ϕā (b̄) åñòü îêîí÷àíèå ñëîâà ϕ(āb̄),êîòîðîå â ñëîâå ϕ(āb̄) ñëåäóåò çà íà÷àëîì ϕ(ā) (åñëè ϕ(ā) = ϕ(āb̄), òî,î÷åâèäíî, ϕā (b̄) = Λ).
Òàêèì îáðàçîì,äåòåðìèíèðîâàííîéîñòàòî÷íîé ôóíê-öèèîñòàòî÷íóþ ôóíêöèþϕ(āb̄) = ϕ(ā)ϕā (b̄).Îòìåòèì, ÷òî îñòàòî÷íàÿ ôóíêöèÿ äåòåðìèíèðîâàííîé ôóíêöèè ϕòàêæå áóäåò äåòåðìèíèðîâàííîé ôóíêöèåé.  ñàìîì äåëå, ïóñòü ϕā îñòàòî÷íàÿ ôóíêöèÿ ôóíêöèè ϕ. Âîçüìåì ïðîèçâîëüíûå ñëîâà b̄, c̄ â àëôàâèòå A. Ñîãëàñíî óñëîâèþ äåòåðìèíèðîâàííîñòè ôóíêöèè ϕ ñëîâî48ϕ(āb̄) åñòü íà÷àëî ñëîâà ϕ(āb̄c̄). Âìåñòå ñ òåì ïî îïðåäåëåíèþ îñòàòî÷íîéôóíêöèè ϕā èìååìϕ(āb̄) = ϕ(ā)ϕā (b̄),ϕ(āb̄c̄) = ϕ(ā)ϕā (b̄c̄).Ñëåäîâàòåëüíî, ñëîâî ϕā (b̄) åñòü íà÷àëî ñëîâà ϕā (b̄c̄) è ϕā äåòåðìèíèðîâàííàÿ ôóíêöèÿ.Äîêàçàííûé ôàêò ïîçâîëÿåò ïðåäñòàâëÿòü çíà÷åíèÿ äåòåðìèíèðîâàííîé ôóíêöèè ϕ íà ñëîâàõ ā = ā1 ā2 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
