С.С. Марченков - Избранные главы дискретной математики (1124120), страница 6
Текст из файла (страница 6)
Èçëîæåííûåñîîáðàæåíèÿ ìû ôîðìàëèçóåì â âèäå ïîíÿòèÿ.Èòàê,A çàäàåòñÿA ={a1 , . . . , ak }, êîíå÷íûì ìíîæåñòâîìQ = {q1 , . . . , qr } èf , êîòîðàÿ îòîáðàæàåò ìíîæåñòâî A × Q â ìíîæåñòâî Q.Ñèìâîëè÷åñêè ýòî áóäåì èçîáðàæàòü òàê: A = (A, Q, f ). Ó÷èòûâàÿ ïðèâåäåííîå âûøå ñîäåðæàòåëüíîå îïèñàíèå ðàáîòû àâòîìàòà A, îáîçíà÷èì÷åðåç x(t) áóêâó àëôàâèòà A, ïîäàâàåìóþ íà âõîä àâòîìàòà A â ìîìåíòâðåìåíè t, à ÷åðåç q(t) åãî ñîñòîÿíèå â ýòîò ìîìåíò âðåìåíè.
Òîãäàôóíêöèîíèðîâàíèå (âî âðåìåíè) àâòîìàòà A ìîæíî âûðàçèòü óðàâíåíèåìïðîñòåéøèé àâòîìàòöèåé ïåðåõîäîâïðîñòåéøåãî àâòîìàòàâõîäíûì àëôàâèòîìñîñòîÿíèéôóíê-q(t) = f (x(t), q(t − 1)).(2.1)Èç ýòîãî óðàâíåíèÿ, ðàâíî êàê èç îïèñàíèÿ ðàáîòû àâòîìàòà, âèäíî,÷òî ïåðåä ïîäà÷åé ñëîâà ā àâòîìàò A íåîáõîäèìî êàê-òî ¾íàñòðîèòü¿,ïðèâåñòè â èñõîäíîå ñîñòîÿíèå. Èíûìè ñëîâàìè, ìû äîëæíû ðåøèòü,â êàêîì èç ñîñòîÿíèé ìíîæåñòâà Q àâòîìàò A íà÷íåò âîñïðèíèìàòüïåðâóþ áóêâó ñëîâà ā êàêîå çíà÷åíèå ìû äîëæíû âûáðàòü â óðàâíåíèè(2.1) äëÿ âåëè÷èíû q(0). Ýòî ñîñòîÿíèå àâòîìàòà A îáû÷íî íàçûâàþòñîñòîÿíèåì, à àâòîìàò ñ âûäåëåííûì íà÷àëüíûì ñîñòîÿíèåì àâòîìàòîì.  êà÷åñòâå íà÷àëüíîãî ñîñòîÿíèÿ ìû, åñëè íåîãîâàðèâàåòñÿ èíîå, áóäåì âûáèðàòü ñîñòîÿíèå q1 .
Òåïåðü èíèöèàëüíûéàâòîìàò A áóäåò îïðåäåëÿòüñÿ ÷åòâåðêîé (A, Q, f, q1 ).  ñâîþ î÷åðåäü, êóðàâíåíèþ (2.1) ìû äîáàâèì íà÷àëüíîå óñëîâèåíà-÷àëüíûìèíèöèàëüíûìq(0) = q1 .(2.2)êàíîíè÷åñêèìè óðàâíåíèÿìèÑîîòíîøåíèÿ (2.1),(2.2) áóäåì íàçûâàòüàâòîìàòà A.Ñóùåñòâóåò åùå íåñêîëüêî ñïîñîáîâ çàäàíèÿ èíèöèàëüíîãî àâòîìàòà.Îäèí èç íàèáîëåå ðàñïðîñòðàíåííûõ çàäàíèå ñ ïîìîùüþÄèàãðàììà Ìóðà ïðåäñòàâëÿåò ñîáîé ãðàôè÷åñêîå çàäàíèå àâòîìàòà. ×òîáû ïîñòðîèòü äèàãðàììó Ìóðà àâòîìàòà A = (A, Q, f, q1 ) ñ rñîñòîÿíèÿìè, íà ïëîñêîñòè âûáèðàþò r ðàçëè÷íûõ òî÷åê (èëè íåïåðåñåêàþùèõñÿ êðóãîâ), êîòîðûå îáîçíà÷àþò ñèìâîëàìè q1 , . . .
, qr . Èç êàæäîéòî÷êè äèàãðàììû Ìóðà ïðîâîäÿò ðîâíî k íàïðàâëåííûõ äóã, êîòîðûåâåäóò â òî÷êè ýòîé äèàãðàììû. Êàæäàÿ äóãà ïîìå÷àåòñÿ îäíîé áóêâîéàëôàâèòà A (ðàçíûå äóãè, âûõîäÿùèå èç îäíîé òî÷êè, ðàçíûìè áóêâàìè). Ïðè ýòîì äóãà, âûõîäÿùàÿ èç òî÷êè qj è ïîìå÷åííàÿ áóêâîé ai , âåäåòäèàãðàììÌóðà.26â òî÷êó ql , ãäå ql = f (ai , qj ).
Íà÷àëüíîå ñîñòîÿíèå q1 îáû÷íî ïîìå÷àåòñÿñèìâîëîì ∗. Íà ðèñ. 1 èçîáðàæåíû ïðèìåðû äèàãðàìì Ìóðà.a1a1a1q1a2q2q1a1q2a2a2a2a)b)a1a1a2q1a1q2q3a2a2c)Ðèñ. 1Ïîä äåéñòâèåì âõîäíîãî ñëîâà ā = ai1 ai2 . . . ain àâòîìàò A ïîñëåäîâàòåëüíî ïåðåõîäèò èç îäíîãî ñîñòîÿíèÿ â äðóãîå. Ïåðåä ïîñòóïëåíèåìáóêâû ai1 àâòîìàò A íàõîäèòñÿ â íà÷àëüíîì ñîñòîÿíèè q1 . Ïîä äåéñòâèåì áóêâû ai1 àâòîìàò A ïåðåõîäèò èç ñîñòîÿíèÿ q1 â ñîñòîÿíèå qj2 =f (ai1 , q1 ), äàëåå ïîä äåéñòâèåì áóêâû ai2 èç ñîñòîÿíèÿ qj2 â ñîñòîÿíèåqj3 = f (ai2 , qj2 ) è ò.ä. Óñëîâèìñÿ ñ÷èòàòü, ÷òî ïîä äåéñòâèåì ïóñòîãî ñëîâà Λ àâòîìàò A íèêóäà íå ïåðåõîäèò, ò.å. îñòàåòñÿ â íà÷àëüíîì ñîñòîÿíèèq1 .Îïðåäåëåííûé íàìè ïðîñòåéøèé èíèöèàëüíûé àâòîìàò ïîêà îáëàäàåòîäíèì ñóùåñòâåííûì íåäîñòàòêîì: íåñìîòðÿ íà òî, ÷òî íà âõîä àâòîìàòàìû ìîæåì ïîäàâàòü ïðîèçâîëüíûå ñëîâà â àëôàâèòå A, íèêàêèõ ñèãíàëîâ î ôóíêöèîíèðîâàíèè àâòîìàòà ìû â îòâåò ïîëó÷àòü íå ìîæåì. Ìûáû õîòåëè, êàê ìèíèìóì, ÷òîáû àâòîìàò ïîñëå ïðî÷òåíèÿ âõîäíîãî ñëîâàâûäàâàë ñèãíàëû òèïà ¾äà¿ è ¾íåò¿.
Èíûìè ñëîâàìè, ìû õîòèì, ÷òîáûíåêîòîðûå ñëîâà â àëôàâèòå A àâòîìàò ¾äîïóñêàë¿ (ïðèíèìàë, ðàñïîçíàâàë), äðóãèå ñëîâà ¾îòâåðãàë¿.Ýòîé öåëè ìîæíî äîñòè÷ü ðàçëè÷íûìè ñïîñîáàìè. Ñàìûé ïðîñòîé èçíèõ âûäåëèòü â ìíîæåñòâå Q íåêîòîðîå ïîäìíîæåñòâî F ¾çàêëþ÷èòåëüíûõ¿ (ôèíàëüíûõ) ñîñòîÿíèé è ñ÷èòàòü, ÷òî ñëîâî āäîïóñêàåòñÿ27(ïðèíèìàåòñÿ, ðàñïîçíàåòñÿ) àâòîìàòîì A, åñëè ïîñëå ïîäà÷è ñëîâà āàâòîìàò A îêàçûâàåòñÿ â îäíîì èç ñîñòîÿíèé ìíîæåñòâà F .
 ïðîòèâíîìñëó÷àå ñ÷èòàåì, ÷òî ñëîâî āàâòîìàòîì A. Òàêèì îáðàçîì,ïîïàäàíèå â îäíî èç ñîñòîÿíèé ìíîæåñòâà F ýòî è åñòü ñèãíàë ¾äà¿,êîòîðûé ¾âûäàåò¿ àâòîìàò â îòâåò íà ïîñòóïèâøåå íà åãî âõîä ñëîâî.Òåïåðü ìû ìîæåì äàòü âïîëíå ñòðîãîå îïðåäåëåíèå(àâòîìàò-ðàñïîçíàâàòåëü). Èòàê, ýòî ìàòåìàòè÷åñêàÿ ìîäåëü ðàñïîçíàþùåãî óñòðîéñòâà ñ êîíå÷íîé ïîìÿòüþ, êîòîðàÿ çàäàåòñÿ íàáîðîì (A, Q, f, q1 , F ), ãäå A = {a1 , . . . , ak } âõîäíîéàëôàâèò àâòîìàòà, Q = {q1 , . . . , qr } ìíîæåñòâî ñîñòîÿíèé àâòîìàòà,f ôóíêöèÿ ïåðåõîäîâ àâòîìàòà, îòîáðàæàþùàÿ ìíîæåñòâî A × Q âìíîæåñòâî Q, q1 íà÷àëüíîå ñîñòîÿíèå àâòîìàòà è F íåïóñòîå ìíîæåñòâî çàêëþ÷èòåëüíûõ ñîñòîÿíèé àâòîìàòà. Îòìåòèì, ÷òî íà÷àëüíîåñîñòîÿíèå q1 ìîæåò áûòü îäíîâðåìåííî è çàêëþ÷èòåëüíûì ñîñòîÿíèåì. ýòîé ãëàâå àâòîìàò áåç âûõîäà áóäåì íàçûâàòü ïðîñòî àâòîìàòîì.Ñ àâòîìàòîì A, êàê ýòî îáúÿñíåíî âûøå, ñâÿçûâàåì ìíîæåñòâî D(A)âñåõ ñëîâ â àëôàâèòå A, êîòîðûå äîïóñêàþòñÿ àâòîìàòîì A.
Äàëåå òàêèå ìíîæåñòâà D(A) áóäåì íàçûâàòüìíîæåñòâàìè èëè êîíå÷íî-àâòîìàòíûìè ÿçûêàìè.  ïàðàãðàôàõ 24 ìû èññëåäóåìêîíå÷íî-àâòîìàòíûå ìíîæåñòâà ñ ðàçëè÷íûõ òî÷åê çðåíèÿ.Íà÷íåì ñ íåêîòîðûõ ïðîñòûõ ïðèìåðîâ. Ðàññìîòðèì àâòîìàòû, äèàãðàììû Ìóðà êîòîðûõ èçîáðàæåíû íà ðèñ. 1. Åñëè â ñëó÷àå a) ïîëîæèòüF = {q1 }, òî ñîîòâåòñòâóþùèé àâòîìàò áóäåò äîïóñêàòü ìíîæåñòâî A∗ ,åñëè æå âçÿòü F = {q2 } òî ïóñòîå ìíîæåñòâî ∅ (ïîñêîëüêó ñîñòîÿíèåq2 íå äîñòèæèìî èç ñîñòîÿíèÿ q1 ). Áîëåå èíòåðåñíûì ïðåäñòàâëÿåòñÿ ñëó÷àé b): ïðè F = {q1 } àâòîìàò äîïóñêàåò ìíîæåñòâî {Λ}, ñîñòîÿùåå òîëüêî èç ïóñòîãî ñëîâà, ïðè F = {q2 } ìíîæåñòâî A∗ áåç ïóñòîãî ñëîâà. Âñëó÷àå c) âûáîð F = {q1 }, F = {q2 } èëè F = {q3 } äàåò ñîîòâåòñòâåííî:ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå {a2 } (âêëþ÷àÿ ïóñòîå ñëîâî); ìíîæåñòâî âñåõ ñëîâ âèäà an2 a1 , ãäå n > 0; ìíîæåñòâî âñåõ ñëîâ âèäà an2 a1 ā, ãäån > 0 è ā 6= Λ.Ðàññìîòðèì åùå äâà ïðèìåðà íåñêîëüêî èíîãî õàðàêòåðà.
Êàê âèäíî èç ðèñ. 2, âõîäíîé àëôàâèò àâòîìàòîâ ñîñòîèò èç îäíîé áóêâû a1 .Íåòðóäíî âèäåòü, ÷òî â ñëó÷àå a) â çàâèñèìîñòè îò âûáîðà F = {q1 } èëèF = {q2 } àâòîìàò áóäåò äîïóñêàòü ëèáî âñå ñëîâà, èìåþùèå ÷åòíóþ äëèíó (âêëþ÷àÿ ïóñòîå ñëîâî Λ, êîòîðîå èìååò äëèíó 0), ëèáî âñå ñëîâà, èìåþùèå íå÷åòíóþ äëèíó. Ïîõîæàÿ êàðòèíà íàáëþäàåòñÿ è â ñëó÷àå b): åñëèF = {q1 }, F = {q2 } èëè F = {q3 }, òî àâòîìàò äîïóñêàåò âñå ñëîâà, èìåþ-îòâåðãàåòñÿàâòîìàòà áåç âûàâòîìàò áåç âûõîäàõîäàêîíå÷íî-àâòîìàòíûìè28ùèå ñîîòâåòñòâåííî äëèíó âèäà 3n, 3n+1 èëè 3n+2 (n > 0). Ýòè ïðèìåðûëåãêî îáîáùèòü íà ìíîæåñòâà ñëîâ ñ äëèíàìè âèäà kn + l (n > 0), ãäåk > 4 è 0 6 l < k.a1q1q1q2a1q2a1a1a)b)a1q3Ðèñ. 2ÓÏÐÀÆÍÅÍÈßÏîñòðîèòü äèàãðàììó Ìóðà èíèöèàëüíîãî àâòîìàòà A = (A, Q, f, q1 ),ãäå A = {a1 , a2 }, Q = {q1 , q2 , q3 , q4 }, à ôóíêöèÿ ïåðåõîäîâ f çàäàåòñÿ òàáëèöåé1.a1a2q1 q2 q3 q4q2 q1 q4 q4q3 q4 q1 q2Ïîñòðîèòü äèàãðàììó Ìóðà äëÿ àâòîìàòîâ ñ âõîäíûì àëôàâèòîì{a1 , a2 }, êîòîðûå äîïóñêàþò ñëåäóþùèå ìíîæåñòâà:a) {a1 , a2 a1 }; b) âñå ñëîâà äëèíû 3; c) âñå ñëîâà, êîòîðûå íà÷èíàþòñÿ ñëîâîì a1 a2 ; d) âñå ñëîâà, êîòîðûå îêàí÷èâàþòñÿ ñëîâîì a1 a1 ; e) âñå ñëîâà,êîòîðûå ñîäåðæàò ñëîâî a2 a2 a1 (â ÷àñòíîñòè, íà÷èíàþòñÿ è îêàí÷èâàþòñÿ ýòèì ñëîâîì).2. 2.
Ïðàâîèíâàðèàíòíàÿ ýêâèâàëåíòíîñòü.Òåîðåòèêî-ìíîæåñòâåííûå îïåðàöèè íàäêîíå÷íî-àâòîìàòíûìè ìíîæåñòâàìèÏóñòü A = (A, Q, f, q1 ) èíèöèàëüíûé àâòîìàò, Q = {q1 , . . . , qr }. Áóäåì ïðåäïîëàãàòü, ÷òî êàæäîå ñîñòîÿíèå èç Qèç íà÷àëüíîãîñîñòîÿíèÿ q1 , ò.å. äëÿ êàæäîãî ñîñòîÿíèÿ qj èç Q íàéäåòñÿ òàêîå ñëîâî âàëôàâèòå A, ïîä äåéñòâèåì êîòîðîãî àâòîìàò A ïåðåõîäèò èç ñîñòîÿíèÿq1 â ñîñòîÿíèå qj .Ðàçîáüåì ìíîæåñòâî A∗ âñåõ ñëîâ â àëôàâèòå A íà r ïîïàðíî íå ïåðåñåêàþùèõñÿ ïîäìíîæåñòâ (êëàññîâ), îòíîñÿ ê êëàññó Ki òå è òîëüêî òåäîñòèæèìî29ñëîâà, êîòîðûå ïåðåâîäÿò àâòîìàò A èç ñîñòîÿíèÿ q1 â ñîñòîÿíèå qi .
Ðàçáèåíèå {K1 , . . . , Kr } ìíîæåñòâà A∗ íà êëàññû ïîðîæäàåò íà ìíîæåñòâåA∗ îòíîøåíèå ýêâèâàëåíòíîñòè ∼: äëÿ ëþáûõ äâóõ ñëîâ ā, b̄ ∈ A∗ ïîëàãàåì ā ∼ b̄ â òîì è òîëüêî òîì ñëó÷àå, êîãäà ñëîâà ā, b̄ âõîäÿò â îäèí è òîòæå êëàññ Ki . Îòíîøåíèå ∼ äåéñòâèòåëüíî ïðåäñòàâëÿåò ñîáîé îòíîøåíèåýêâèâàëåíòíîñòè: îíî ðåôëåêñèâíî (äëÿ ëþáîãî ñëîâà ā îòíîøåíèå ā ∼ āâûïîëíÿåòñÿ òðèâèàëüíûì îáðàçîì), îíî ñèììåòðè÷íî (èç ā ∼ b̄ ñëåäóåòb̄ ∼ ā) è îíî òðàíçèòèâíî (èç ā ∼ b̄ è b̄ ∼ c̄ ñëåäóåò ā ∼ c̄).
Áóäåì íàçûâàòü îòíîøåíèå ∼, ïîðîæäåííîéàâòîìàòîì A.Ïîìèìî îïðåäåëÿþùèõ ñâîéñòâ îòíîøåíèÿ ýêâèâàëåíòíîñòè îòíîøåíèå ∼ îáëàäàåò åùå îäíèì ñâîéñòâîì, õàðàêòåðíûì òîëüêî äëÿ àâòîìàòîâ. Ýòî ñâîéñòâî: åñëè ā ∼ b̄ è c̄ ëþáîå ñëîâîâ àëôàâèòå A, òî āc̄ ∼ b̄c̄.
Ñâîéñòâî ïðàâîé èíâàðèàíòíîñòè äëÿ îòíîøåíèÿ ∼ ëåãêî óñòàíàâëèâàåòñÿ íåïîñðåäñòâåííî èç îïðåäåëåíèÿ îòíîøåíèÿ ∼ è ðàçáèåíèÿ {K1 , . . . , Kr }: åñëè ïîä äåéñòâèåì ñëîâ ā, b̄ àâòîìàòA ïåðåõîäèò èç ñîñòîÿíèÿ q1 â îäíî è òî æå ñîñòîÿíèå èç ìíîæåñòâàQ, òî, ðàçóìååòñÿ, ïîä äåéñòâèåì ñëîâ āc̄ è b̄c̄ àâòîìàò A òàêæå áóäåòïåðåõîäèòü èç ñîñòîÿíèÿ q1 â îäíî è òî æå ñîñòîÿíèå èç Q.Ðàññìîòðèì íà ìíîæåñòâå A∗ ïðîèçâîëüíîå ïðàâîèíâàðèàíòíîå îòíîøåíèå ýêâèâàëåíòíîñòè ∼. Îíî çàäàåò ðàçáèåíèå ìíîæåñòâà A∗ íà ïîïàðíî íå ïåðåñåêàþùèåñÿ êëàññû: ê îäíîìó êëàññó îòíîñÿòñÿ âñå ñëîâà,êîòîðûå ýêâèâàëåíòíû â ñìûñëå îòíîøåíèÿ ∼.
Âîîáùå ãîâîðÿ, ÷èñëîêëàññîâ îòíîøåíèÿ ∼ ìîæåò îêàçàòüñÿ áåñêîíå÷íûì. Áóäåì ãîâîðèòü,÷òî îòíîøåíèå ∼ èìååò, åñëè ÷èñëî òàêèõ êëàññîâ êîíå÷íî.Ïóñòü íà ìíîæåñòâå A∗ çàäàíî ïðîâîèíâàðèàíòíîå îòíîøåíèå ýêâèâàëåíòíîñòè ∼ êîíå÷íîãî èíäåêñà è K1 , . . . , Kr âñå êëàññû ýòîé ýêâèâàëåíòíîñòè. Áóäåì ïðåäïîëàãàòü, ÷òî ñëîâî Λ âõîäèò â êëàññ K1 .Îïðåäåëèì êîíå÷íûé èíèöèàëüíûé àâòîìàò K ñ âõîäíûì àëôàâèòîì Aè ìíîæåñòâîì ñîñòîÿíèé {K1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
