А.Б. Угольников - Лекции по дискретной математике (1083729), страница 11
Текст из файла (страница 11)
6: Ïðèìåð îáîáù¼ííîãî èñòî÷íèêà.Ýòîò èñòî÷íèê ïðåäñòàâëÿåò ñëîâàÏðèìåð 2.ac, acac, abbbc, abc, abbcacè äð.Èñòî÷íèêv1 ·ïðåäñòàâëÿåò ñîáûòèå·vk∅.Ëåììà. Åñëè ñîáûòèå ðåãóëÿðíî, òî íàéä¼òñÿ îáîáùåííûé èñòî÷íèê, åãî ïðåäñòàâëÿþùèé.Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî áóäåì âåñòè èíäóêöèåé ïî ÷èñëó ýëåìåíòàðíûõ îïåðàöèé ∪, ·è<>èñïîëüçóåìûõ äëÿ ïîëó÷åíèÿ ñîáûòèÿE. êà÷åñòâå áàçû èíäóêöèè ïðèâåä¼ì îáîáù¼ííûå èñòî÷íèêè ïîðîæäàþùèå ýëåìåíòàðíûå ñîáûòèÿ:∅ : v1 ··vka1{a1 } : v1 · −→ ·vk...am{am } : v1 · −→·vkn ýëåìåíE èñïîëüçîâàíà n + 1 îïåðàöèÿ. Òîãäà E ïîëó÷åíîîäíèì èç òð¼õ íèæåñëåäóþùèõ ñïîñîáîâ, ãäå E1 , E2 èñïîëüçóþò íå áîëåå n ýëåìåíòàðíûõ îïåðàöèé,Èòàê, ïóñòü ìû óìååì ïðåäñòàâëÿòü ñîáûòèÿ, ïîëó÷åííûå ñ èñïîëüçîâàíèåì íå áîëååòàðíûõ îïåðàöèé.
Ïóñòü äëÿ ïîëó÷åíèÿ ñîáûòèÿñëåäîâàòåëüíî äëÿ íèõ îáîáù¼ííûå èñòî÷íèêè ìîãóò áûòü ïîñòðîåíû:1)2)3)E = E1 ∪ E2 (ñì. Ðèñ. 7).E = E1 E2 (ñì. Ðèñ. 8).E =< E1 > (ñì. Ðèñ. 9).Ëåììà äîêàçàíà.Òåîðåìà. Ïóñòü Å ðåãóëÿðíîå ñîáûòèå, òîãäà Å ïðåäñòàâèìî (ñ ïîìîùüþ êîíå÷íîãî àâ-òîìàòà).56Ðèñ. 7: Äîêàçàòåëüñòâî ïóíêòà 1.Ðèñ. 8: Äîêàçàòåëüñòâî ïóíêòà 2.B = {0, 1}, B 0 = {1}. Ïî ïðåäûäóùåé ëåììå ñóùåñòâóåò îáîáù¼ííûé èñòî÷íèê I = (W, E), òàêîé ÷òî [I] = E. Ïóñòü W = {v1 , ..., vn }, ãäå v1 íà÷àëüíàÿ, vn ∗êîíå÷íàÿ âåðøèíû.
Äëÿ α ∈ A è v ∈ W îïðåäåëèì ìíîæåñòâà:Äîêàçàòàëüñòâî.Âîçüì¼ìΘ(α, v) = {v̂ ∈ W | ∃p : v → v̂ : αp = α}Îïðåäåëèì ìíîæåñòâî ñîñòîÿíèé, êàêQ = {q1 , ..., q2n } ìíîæåñòâî âñåâîçìîæíûõ ïîäìíîæåñòâW. êà÷åñòâå íà÷àëüíîãî ñîñòîÿíèÿ âîçüì¼ìq1 = {v1 }.Îïðåäåëèì ôóíêöèþ ïåðåõîäà:G(a, q) =[Θ(a, v)v∈q ìíîæåñòâî âåðøèí, â êîòîðûå ìîæíî ïîïàñòü èç äàííîãî ìíîæåñòâà âåðøèíöèþFîïðåäåëèì òàê:F (a, q) =1, vn ∈ G(a, q)0, èíà÷å ìîæíî ëè ïîïàñòü â êîíå÷íóþ âåðøèíó èç äàííîãî ìíîæåñòâà ïî áóêâå57a.qïî áóêâåa.Ôóíê-Ðèñ. 9: Äîêàçàòåëüñòâî ïóíêòà 3.Vq1 (A, B, Q, F, G) ïîñðåäñòâîì B 0 ïðåäñòàâëÿåò â òî÷íîñòè [I]. Äåéñòâè0ñ ïîìîùüþ Vq1 ïîñðåäñòâîì B ⇔ F (α, q1 ) = 1 ⇔ vn ∈ G(α, q1 ) ⇔ vn ∈Ïîëó÷åííûé àâòîìàòòåëüíî, α ïðåäñòàâèìîΘ(α, v1 ) ⇔ α ∈ [I]. Ïðåäïîñëåäíèé ïåðåõîä, åñëè è íå ÿâëÿåòñÿâàåòñÿ. Ïîñêîëüêó α ∈ [I] ⇔ α ∈ E, òî òåîðåìà äîêàçàíà.î÷åâèäíûì, òî î÷åíü ëåãêî äîêàçû-Ëåììà 1.
Ïóñòü X, C, D ñîáûòèÿ. ÒîãäàX = D ∪ XC ⇔X =D∪D <C >Äîêàçàòåëüñòâî.ÏóñòüX =D∪D <C >.ÒîãäàD ∪ XC = D ∪ (D ∪ D < C >)C = D ∪ (DC ∪ D < C > C) == D ∪ D(C∪ < C > C) = D ∪ D < C >= XÎáðàòíî: ïóñòüX = D ∪ XC .ÄîêàçàòåëüñòâîX = D∪D < C >ðàçîáü¼ì íà äîêàçàòåëüñòâàäâóõ âêëþ÷åíè.X ⊆ D ∪ D < C > . Ïðåäïîëîæèì ïðîòèâíîå: ïóñòü ñóùåñòâóåò òàêîå α ∈ X,α 6∈ D ∪ D < C > .
Ñðåäè âñåõ òàêèõ α âûáåðåì ñëîâî íàèìåíüøåé äëèíû. α 6∈ D ⇒α ∈ XC ⇒ α = α1 α2 , ãäå α1 ∈ X, α2 ∈ C. Ïðè÷¼ì λ(α1 ) < λ(α) ⇒ α1 ∈ D ∪ D < C >⇒ α = α1 α2 ∈ (D ∪ D < C >)C = DC ∪ D < C > C = D(C∪ < C > C) = = D < C >⊆ D ∪ D < C >à) Ïîêàæåì, ÷òî÷òî ïðîòèâîðå÷èå.X ⊇ D ∪ D < C > . Îïÿòü ïðåäïîëàãàåì ïðîòèâíîå: ñóùåñòâóåò α ∈ D ∪ D <α 6∈ X. Îïÿòü ñðåäè âñåõ òàêèõ α âûáåðåì íàèìåíüøåå ïî äëèíå: α 6∈ X ⇒ α 6∈á) Ïîêàæåì, ÷òîC >,òàêîå ÷òîñì. à)D ⇒ α ∈ D < C > = = (D ∪ D < C >)C ⇒ α = α1 α2 , ãäå α1 ∈ D ∪ D < C >, α2 ∈ C.λ(α1 ) < λ(α), òî α1 ∈ X ⇒ α = α1 α2 ∈ XC ⊆ X ïðîòèâîðå÷èå.
Ëåììà äîêàçàíà.Çàìå÷àíèå. Åñëè ñîáûòèÿ C è D ðåãóëÿðíû è äëÿ ñîáûòèÿ X âûïîëíÿåòñÿ ðàâåíñòâîX = D ∪ XC,òî ïî äîêàçàííîé òîëüêî ÷òî ëåììå ñëåäóåò, ÷òî X ðåãóëÿðíî.Ïðèìåð íåðåãóëÿðíîãî ñîáûòèÿ.Îáîçíà÷èì:0k = |{z}0...0k1k = |{z}1...1k58Ò.ê.Ðàññìîòðèì ìíîæåñòâî ñëîâ:E = {0k 1k , k = 1, 2, 3, ...}Ýòî ñîáûòèå íå ÿâëÿåòñÿ ðåãóëÿðíûì.Äîêàçàòåëüñòâî.Ïðåäïîëîæèì ïðîòèâíîå: ïóñòüE ðåãóëÿðíî. Òîãäà ïî äîêàçàííîìó âûøåñóùåñòâóåò êîíå÷íûé àâòîìàòVq1 = ({0, 1}, {0, 1}, Q, F, G),ãäåQ = {q1 , ..., qn },òàêîé ÷òîα ∈ E ⇔ F (α, q1 ) = 1.Ðàññìîòðèìn+1çíà÷åíèå ôóíêöèèG:G(0, q1 ), G(02 , q1 ), ..., G(0n+1 , q1 )Íàéäóòñÿ òàêèåièj,÷òîi 6= jèG(0i , q1 ) = G(0j , q1 ).Äëÿ íèõ:1 = F (0i 1i , q1 ) = F (1i , G(0i , q1 )) = F (1i , G(0j , q1 )) = F (0j 1i , q1 ) ïðîòèâîðå÷èå.Ëåììà 2.
Ïóñòü âûïîëíÿåòñÿ n ðàâåíñòâ:Xi = R0i ∪ X1 R1i ∪ ... ∪ Xn Rni , i = 1, ..., n,(∗)ãäå Xi ñîáûòèÿ, Rji ðåãóëÿðíûå ñîáûòèÿ i = 1, ..., n, j = 0, 1, ..., n. Òîãäà Xi ðåãóëÿðíûåñîáûòèÿ i = 1, ..., n.Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ïðîâåä¼ì èíäóêöèåé ïî n. Áàçîé (n = 1) ÿâëÿåòñÿ Çàìå÷àíèåê Ëåììå 1. Ïóñòü óòâåðæäåíèå äîêàçàíî ïðè âñåõ n = 1, ..., k − 1, ïîêàæåì, ÷òî îíî ñïðàâåäëèâî èïðè n = k.  ïåðâîì óðàâíåíèè îáîçíà÷èì D = R01 ∪ X2 R21 ∪ ... ∪ Xk Rn1 , C = R11 . ÒîãäàX1 = D ∪ CX1ïî Ëåììå1=⇒X1 = D ∪ D < C >X1 â îñòàëüíûå óðàâíåíèÿ è ðàñêðîåì âûðàæåíèÿ äëÿ D è C.X2 , ..., Xk ñ ðåãóëÿðíûìè êîýôôèöèåíòàìè. Ïî ïðåäïîëîæåíèþðåãóëÿðíûå ñîáûòèÿ. Ïîýòîìó è X1 ðåãóëÿðíî.
Ëåììà äîêàçàíà.Ïîäñòàâèì ýòî âûðàæåíèå äëÿÏîëó÷èì ñèñòåìó âèäà(∗)èíäóêöèè å¼ ðåøåíèå åñòüÒåîðåìàñòàâèìî.(Êëèíè.)Äîêàçàòåëüñòâî.äëÿÑîáûòèå E ÿâëÿåòñÿ ðåãóëÿðíûì òîãäà è òîëüêî òîãäà, êîãäà E ïðåä îäíó ñòîðîíó òåîðåìà äîêàçàíà âûøå. Äîêàæåì òåïåðü, ÷òî âñÿêîå ïðåä-ñòàâèìîå ñîáûòèå ðåãóëÿðíî. Ïóñòü äàí èíèöèàëüíûé êîíå÷íûé àâòîìàò:Vq0 = (A, B, Q, F, G)|Q| = n, Q = {q1 , ..., qn }, B 0 ⊆ B, E = {α|F (α, q1 ) ∈ B 0 }.Îïðåäåëèì ñîáûòèÿ:Ei = {α ∈ A∗ \ {Λ}|G(α, q1 ) = qi }, i = 1, ..., nÊi = {a ∈ A|F (a, qi ) ∈ B 0 }, i = 1, ..., nÎ÷åâèäíî, ÷òî â ñèëó êîíå÷íîñòèÊiðåãóëÿðíû.
Ïîêàæåì, ÷òîEiðåãóëÿðíû. Îïðåäåëèì ñîáûòèÿRji = {a ∈ A|G(a, qj ) = qi }, i = 1, ..., n, j = 1, ..., nßñíî, ÷òî â ñèëó èõ êîíå÷íîñòèRjiðåãóëÿðíû. Ïîêàæåì, ÷òîEi = R1i ∪ E1 R1i ∪ ... ∪ En Rnia)α ∈ Ei , α = a ∈ A ⇔ G(a, q1 ) = qi ⇔ α = a ∈ R1i59(∗∗)α = α0 a ∈ Ei , α0 6= Λ, a ∈ A ⇔ qi = G(α0 a, q1 ) = G(a, G(α0 , q1 )) = = G(a, qj ) ⇔ α0 ∈ Ej , a ∈ RjiÈç (∗∗) ïî ëåììå 2 ñëåäóåò, ÷òî Ei ðåãóëÿðíû. Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà òåîðåìû ïîêà-á)æåì, ÷òîE = Eˆ1 ∪ E1 Eˆ1 ∪ ... ∪ En Eˆnà) Ïîêàæåì âêëþ÷åíèå:E ⊆ Eˆ1 ∪ E1 Eˆ1 ∪ ...
∪ En Eˆnα ∈ E. Åñëè α = a ∈ A, òî, î÷åâèäíî, α ∈ Eˆ1 .F (a, G(α0 , q1 )) = F (a, qi ) ∈ B 0 ⇒ α0 ∈ Ei , a ∈ Êi .ÏóñòüÅñëèα = α0 a, α0 6= Λ,òîF (α0 a, q1 ) ∈ B 0 ⇒á) Îáðàòíîå âêëþ÷åíèå:E ⊇ Eˆ1 ∪ E1 Eˆ1 ∪ ... ∪ En Eˆnα ∈ Eˆ1 ∪ E1 Eˆ1 ∪ ... ∪ En Eˆn . Åñëè α = a ∈ A ⇒ a ∈ Eˆ1 ⇒ a = α ∈ E. Åñëè α = α0 a ⇒ α0 a ∈Ei Êi ⇒ α0 ∈ Ei , a ∈ Êi ⇒ F (α, q1 ) = F (α0 a, q1 ) = = F (a, G(α0 , q1 )) = F (a, qi ) ∈ B 0 .ÏóñòüÒåîðåìà äîêàçàíà.60Ëåêöèÿ 15.Êîíå÷íûå àâòîìàòû (ïðîäîëæåíèå).èñòî÷íèêà. Èñòî÷íèêîì íàçûâàåòñÿ îðèåíòèðîâàííûé ãðàô J = (W, E) ñ âûv1 ∈ W è êîíå÷íûìè âåðøèíàìè vi1 , ..., vik ∈ W (1 6 k 6 |W |),êîòîðîãî ïîìå÷åíî áóêâîé àëôàâèòà A : e ∈ E ⇒ µ(e) ∈ A (ïóñòîå ñëîâî íå ìîæåòÂâåä¼ì ïîíÿòèåäåëåííîé íà÷àëüíîé âåðøèíîéêàæäîå ðåáðîâûñòóïàòü â êà÷åñòâå ìåòêè ðåáðà). Êàê è äëÿ îáîáù¼ííîãî èñòî÷íèêà, äëÿ èñòî÷íèêà ââîäèòñÿìíîæåñòâî ñëîâ, ïðåäñòàâèìûõ èì:[J] = {α ∈ A∗ \ {Λ}|∃v 0 êîíå÷íàÿ âåðøèíà,∃p: v1 → v 0 : αp = α}Óòâåðæäåíèå 1.
Ïóñòü J = (W, E) èñòî÷íèê. Òîãäà ñóùåñòâóåò îáîáù¼ííûé èñòî÷íèêI = (W 0 , E 0 ), òàêîé ÷òî [J] = [I].Äîêàçàòåëüñòâî.Äîêàçàòåëüñòâî ïðîâåä¼ì â äðåâíåãðå÷åñêîé ìàíåðå: ÑÌÎÒÐÈ:Ðèñ. 10: Ïåðåõîä îò èñòî÷íèêà ê îáîáùåííîìó èñòî÷íèêó.Ïîÿñíåíèå: äîáàâèëè åù¼ îäíó âåðøèíóv0è êîíå÷íîé òåïåðü íàçûâàåì òîëüêî å¼.Óòâåðæäåíèå 2. Ïóñòü M ïðåäñòàâèìî (ñ ïîìîùüþ èíèöèàëüíîãî àâòîìàòà).
Òîãäà ñóùåñòâóåò èñòî÷íèê J = (W, E), òàêîé ÷òî M = [J].Äîêàçàòåëüñòâî. Ïóñòü Vq1 èíèöèàëüíûé àâòîìàò, ïðåäñòàâëÿþùèé M ñ ïîìîùüþ B 0 :V = (A, B, Q, F, G)Q = {q1 , ..., qn }|A| = m, |B| = p, B 0 ⊆ BÎïðåäåëèì ìíîæåñòâî âåðøèí èñòî÷íèêà:W = {v1 = (Λ, q1 ), vli = (bl , qi ), 1 6 l 6 p, 1 6 i 6 n}vli = (bl , qi ) êîíå÷íàÿ, åñëè, è òîëüêî åñëè bl ∈ B 0 .
Âåðøèíû (bl1 , qi ) è (bl2 , qj )ñîåäèíåíû ðåáðîì e îò ïåðâîé êî âòîðîé âåðøèíå, åñëè, è òîëüêî åñëè ñóùåñòâóåò a ∈ A, òàêîå ÷òîG(a, qi ) = qj è F (a, qi ) = = bl2 . Ïðè ýòîì µ(e) = a. Ëåãêî ïîíÿòü, ÷òî M = [J].ïðè ýòîì âåðøèíàÏîäûòîæèâàÿ óñòàíîâëåííóþ â íåñêîëüêèõ ïðåäûäóùèõ óòâåðæäåíèÿõ ñâÿçü ìåæäó ðàçëè÷íûìè ñïîñîáàìè çàäàíèÿ ñîáûòèé, ñîñòàâèì äèàãðàììó âëîæåííîñòè, ïîêàçûâàþùóþ, ÷òî íà ñàìîìäåëå âñå ñïîñîáû çàäàíèÿ ñîáûòèé ýêâèâàëåíòíû: ñì. Ðèñ. 11.Ïîñòàâèì âîïðîñ î ðàâåíñòâå äâóõ ñîáûòèé, çàäàâàåìûõ èíèöèàëüíûìè êîíå÷íûìè àâòîìàòàìè.Ââåä¼ì íåêîòîðûå îïðåäåëåíèÿ.
Ãîâîðèì, ÷òî äëÿ êîíå÷íûõ àâòîìàòîâ61V = (A, B, Q, F, G), V 0 =Ðèñ. 11: Äèàãðàììà óñòàíîâëåííîé âëîæåííîñòè êëàññîâ ñîáûòèé.(A, B, Q0 , F 0 , G0 )äâà íà÷àëüíûõ ñîñòîÿíèÿq1 ∈ Q, q2 ∈ Q0 ýêâèâàëåíòíû,è ïèøåìq1 ∼ q2 ,åñëèk∗α ∈ A fVq1 (α) = fVq02 (α). Ãîâîðèì, ÷òî îíè ê-ýêâèâàëåíòíû, è ïèøåì q1 ∼ q2 , åñëè äëÿkëþáîãî α ∈ A = {a1 ...ak |ai ∈ A} fVq (α) = fV 0 (α).
Ãîâîðèì òàêæå, ÷òî ñàìè êîíå÷íûå àâòîìàòûq21ýêâèâàëåíòíû V ∼ V 0 , åñëè äëÿ ëþáîãî q ∈ Q ñóùåñòâóåò q 0 ∈ Q0 , òàêîé ÷òî q ∼ q 0 , è äëÿ ëþáîãîq 0 ∈ Q0 ñóùåñòâóåò q ∈ Q, òàêîé ÷òî q 0 ∼ q.äëÿ ëþáîãîÂîïðîñû ýêâèâàëåíòíîñòè ñîñòîÿíèé è àâòîìàòîâ ïîìîãàþò ðåøèòü íåñêîëüêî ñëåäóþùèõ óòâåðæäåíèé.Ëåììà. Ïóñòü äëÿ íåêîòîðîãî àâòîìàòà V = (A, B, Q, F, G) ñóùåñòâóåò äâà íå ýêâèâàkëåíòíûõ, íî ê-ýêâèâàëåíòíûõ ñîñòîÿíèÿ: q1 ∼ q2 , q1 6∼ q2 . Òîãäà äëÿ íåãî íàéäóòñÿ äâà êk6∼ýêâèâàëåíòíûõ, íî íå ê+1-ýêâèâàëåíòíûõ ñîñòîÿíèÿ: q10 ∼ q20 , q10 k + 1 q20 .Äîêàçàòåëüñòâî.
Ïóñòü α = α(1)...α(l) íàèìåíüøåå ïî äëèíå ñëîâî, òàêîå ÷òî fVq0 (α) 6=fVq1 (α). Ïîëîæèì α0 = α(1)...α(l − k − 1). Òîãäà íåòðóäíî ïðîâåðèòü, ÷òî â êà÷åñòâå q10 , q20 ìîæíî0000âçÿòü q1 = G(α , q1 ), q2 = = G(α , q2 ).Òåîðåìà(Ìóð).Ïóñòü V = (A, B, Q, F, G), q1 , q2 ∈ Q, |Q| = n. Òîãäàn−1q1 ∼ q2 ⇔ q1 ∼ q2Äîêàçàòåëüñòâî. îäíó ñòîðîíó òåîðåìà î÷åâèäíà.
Äîêàæåì â äðóãóþ. ÏóñòüÎïðåäåëèì ðàçáèåíèå ìíîæåñòâà ñîñòîÿíèéQn−1q1 ∼ q2 .íà êëàññû:Rk = {Qk1 , ..., Qkrk }ïî ñëåäóþùåìó ïðàâèëó:1.2.Qki ⊆ Q, Qki 6= ∅rkS=Qi=1Qki ∩ Qkj =0k4. ∀q, q ∈ Qi3.∅, i 6= jkq ∼ q0k∀q ∈ Qki , ∀q 0 ∈ Qkj , i 6= j q 6∼ q 0kÒ.å. {Qi } ðàçáèåíèå ìíîæåñòâà ñîñòîÿíèé íà ê-ýêâèâàëåíòíûå (íåòðóäíî ïðîâåðèòü, ÷òî ê-ýêâèâàëåíòíîñòü5. îòíîøåíèå ýêâèâàëåíòíîñòè). Îòìåòèì î÷åâèäíîå ñâîéñòâî:1 6 |R1 | 6 ... 6 |Rn | 6 n62(êàæäîå ñëåäóþùåå ðàçáèåíèå ÿâëÿåòñÿ ïîäðàçáèåíèåì ïðåäûäóùåãî). Àïðèîðè âîçìîæíû äâå ñèòóàöèè:1) Ñóùåñòâóåò1 6 k 6 n−1 òàêîå, ÷òî |Rk | = |Rk+1 |. Íî òîãäà, ò.ê.
Rk+1 ÿâëÿåòñÿ ïîäðàçáèåíèåìkk+1Rk+1 = Rk . Ýòî çíà÷èò, ÷òî äëÿ ëþáûõ q, q 0 ∈ Q, òàêèõ ÷òî q ∼ q 0 âûïîëíÿåòñÿ q ∼ q 0 . Íî0ýòî îçíà÷àåò, ÷òî q ∼ q ïðåäïîëàãàÿ ïðîòèâíîå ïðèõîäèì ê ïðîòèâîðå÷èþ ñ ëåììîé.2) Òàêîãî k íå ñóùåñòâóåò. Ïîêàæåì, ÷òî ïðè n > 2 ýòà ñèòóàöèÿ íåâîçìîæíà. Äåéñòâèòåëüíî, âýòîì ñëó÷àå |Ri | = i.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
