1610906281-d25a58898a45262b0b837c281ba962eb (Лекции Когабаев Соболева), страница 3

. . , n} îäíîçíà÷íî çàäà¼òÑëåäñòâèå 4.ñÿ ñâîåé õàðàêòåðèñòè÷åñêîé ôóíêöèåé XA : {1, . . . , n} −→ {0, 1}, îïðåäåë¼ííîé ïîñõåìå(1, åñëè x ∈ A,XA (x) =0, åñëè x ∈/ A.Áîëåå òîãî, êàæäàÿ ôóíêöèÿ âèäà f : {1, . . . , n} −→ {0, 1} ÿâëÿåòñÿ õàðàêòåðèñòè÷åñêîé äëÿ íåêîòîðîãî A ⊆ {1, . . . , n}. Ïî ïðåäëîæåíèþ 3 êîëè÷åñòâî òàêèõ ôóíêöèéðàâíî 2n .Ïóñòü X , Y êîíå÷íûå ìíîæåñòâà, kXk = k, kY k = n è k 6 n.n!.×èñëî âñåõ èíúåêòèâíûõ ôóíêöèé âèäà f : X −1−1−→ Y ðàâíî(n − k)!Ïðåäëîæåíèå 5.Äîêàçàòåëüñòâî.

Ïóñòü X = {1, . . . , k}, Y= {1, . . . , n}. Çíà÷åíèå f (1) âûáèðàåòñÿn ñïîñîáàìè èç ìíîæåñòâà {1, . . . , n}. Çíà÷åíèå f (2) âûáèðàåòñÿ n − 1 ñïîñîáîì èçìíîæåñòâà {1, . . . , n} \ {f (1)}. Çíà÷åíèå f (3) âûáèðàåòñÿ n − 2 ñïîñîáàìè èç ìíîæåñòâà {1, . . . , n} \ {f (1), f (2)}.

Ðàññóæäàÿ äàëåå àíàëîãè÷íûì îáðàçîì, îêîí÷àòåëüíîn!.ïîëó÷àåì, ÷òî êîëè÷åñòâî ôóíêöèé ðàâíî n·(n − 1)· . . . ·(n − k + 1) =(n − k)!Êîìáèíàòîðíàÿ êîíôèãóðàöèÿ èç ïðåäëîæåíèÿ 5 ðàâíîñèëüíà çàäà÷åïîäñ÷åòà ÷èñëà ñïîñîáîâ ðàçìåùåíèÿ k ðàçëè÷èìûõ ïðåäìåòîâ ïî n ÿùèêàì, íå áîëåå÷åì ïî îäíîìó â ÿùèê.Çàìå÷àíèå.Îïðåäåëåíèå.×èñëîn!, ãäå k 6 n, íàçûâàåòñÿ(n − k)!÷èñëîì ðàçìåùåíèé è îáîçíà-÷àåòñÿ ÷åðåç Akn .×èñëî âñåõ ïåðåñòàíîâîê n-ýëåìåíòíîãî ìíîæåñòâà ðàâíî n!.Äîêàçàòåëüñòâî. Êàæäàÿ ïåðåñòàíîâêà ìíîæåñòâà X = {1, . .

. , n} èìååò âèä fÑëåäñòâèå 6.1−1X −−→ X . Ïî ïðåäëîæåíèþ 5 êîëè÷åñòâî òàêèõ ôóíêöèé ðàâíîAnn:= n!.Ïóñòü X , Y êîíå÷íûå ìíîæåñòâà, kXk = k, kY k = n è k 6 n.×èñëî âñåõ ñòðîãî âîçðàñòàþùèõ ôóíêöèé âèäà f : X → Y ðàâíî k!(nn!− k)! .Ïðåäëîæåíèå 7.Äîêàçàòåëüñòâî. Îáîçíà÷èì A = {f: X → Y | f èíúåêòèâíàÿ ôóíêöèÿ}, C ={f : X → Y | f ñòðîãî âîçðàñòàþùàÿ ôóíêöèÿ}. Ïî ïðåäëîæåíèþ 5 ïîëó÷àåìn!kAk =.(n − k)!Îïðåäåëèì íà ìíîæåñòâå A áèíàðíîå îòíîøåíèå ∼ ñëåäóþùèì îáðàçîì:f ∼ g ⇐⇒ range(f ) = range(g).Íåòðóäíî âèäåòü, ÷òî ∼ ÿâëÿåòñÿ ýêâèâàëåíòíîñòüþ íà A. Çàìåòèì, ÷òî åñëè f ∼ g , òîf è g îòëè÷àþòñÿ ëèøü ïåðåñòàíîâêîé çíà÷åíèé ôóíêöèè. Ñëåäîâàòåëüíî, â êàæäîìŸ 3.

Ýëåìåíòû êîìáèíàòîðèêè11êëàññå ýêâèâàëåíòíîñòè ñòîëüêî æå ýëåìåíòîâ ñêîëüêî ïåðåñòàíîâîê k -ýëåìåíòíîãîìíîæåñòâà, òî åñòü k!. Òàêèì îáðàçîì, êîëè÷åñòâî ýëåìåíòîâ â ôàêòîð-ìíîæåñòâån!.ðàâíî kA/∼k = Akn /k! =k!(n − k)!Ïîñòðîèì òåïåðü áèåêöèþ ϕ : A/∼ → C . Ïóñòü f /∼ ïðîèçâîëüíûé êëàññ ýêâèâàëåíòíîñòè, îí ñîñòîèò èç k! èíúåêòèâíûõ ôóíêöèé ñ îäíîé è òîé æå îáëàñòüþçíà÷åíèé.

ßñíî, ÷òî âíóòðè êëàññà f /∼ ñóùåñòâóåò åäèíñòâåííàÿ ôóíêöèÿ f0 , êîòîðàÿ ÿâëÿåòñÿ ñòðîãî âîçðàñòàþùåé. Ïîëîæèì ϕ(f /∼) = f0 . Òîãäà ϕ èíúåêòèâíà, ò.ê.åñëè f /∼ =6 g/∼, òî ó ϕ(f /∼) è ϕ(g/∼) ðàçëè÷íûå îáëàñòè çíà÷åíèé. Êðîìå ýòîãî, ϕñþðúåêòèâíà, ò.ê. åñëè f ∈ C , òî ϕ(f /∼) = f .n!.Òàêèì îáðàçîì, kCk = kA/∼k =k!(n − k)!Êîìáèíàòîðíàÿ êîíôèãóðàöèÿ èç ïðåäëîæåíèÿ 7 ðàâíîñèëüíà çàäà÷åïîäñ÷åòà ÷èñëà ñïîñîáîâ ðàçìåùåíèÿ k íåðàçëè÷èìûõ ïðåäìåòîâ ïî n ÿùèêàì, íåáîëåå ÷åì ïî îäíîìó â ÿùèê.Çàìå÷àíèå.Îïðåäåëåíèå.×èñëîçíà÷àåòñÿ ÷åðåç Cnk .n!, ãäå k 6 n, íàçûâàåòñÿk!(n − k)!÷èñëîì ñî÷åòàíèé è îáî-Ãëàâà IIÊîíå÷íûå àâòîìàòû è ôîðìàëüíûåãðàììàòèêèŸ 4.Äåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòûÊîíå÷íûå àâòîìàòû îòíîñÿòñÿ ê êëàññó ñëîâàðíûõ àëãîðèòìîâ.

Ñ ïîìîùüþ êîíå÷íûõ àâòîìàòîâ ìîæíî ðåøàòü çàäà÷è èç äîñòàòî÷íî øèðîêîãî ñåìåéñòâà àëãîðèòìè÷åñêèõ ïðîáëåì. Íàïðèìåð, òåõíîëîãèÿ ïðîåêòèðîâàíèÿ ìèêðîñõåì îñíîâàíà íàðåçóëüòàòàõ òåîðèè àâòîìàòîâ. Äðóãîé ïðèìåð ýòî êîìïèëÿòîðû, ïåðåðàáàòûâàþùèå òåêñò ïðîãðàììû, íàïèñàííîé íà ÿçûêå ïðîãðàììèðîâàíèÿ âûñîêîãî óðîâíÿ,â ïðîãðàììó íà ìàøèííîì ÿçûêå. Ðàáîòà ëþáîãî òàêîãî êîìïèëÿòîðà ñîñòîèò èçäâóõ ñòàäèé. Ïåðâàÿ ñòàäèÿ ëåêñè÷åñêèé àíàëèç òåêñòà, êîòîðûé ðåàëèçóåòñÿ ñïîìîùüþ îïðåäåëåííîãî êîíå÷íîãî àâòîìàòà.

Âòîðàÿ ñòàäèÿ ñèíòàêñè÷åñêèé àíàëèç, êîòîðûé îñóùåñòâëÿåòñÿ ñ ïîìîùüþ àâòîìàòà ñ ìàãàçèííîé ïàìÿòüþ. Îäíàêî,êàê áóäåò âèäíî ïîçäíåå, íå ëþáàÿ àëãîðèòìè÷åñêàÿ çàäà÷à ïîääàåòñÿ ðåøåíèþ ñïîìîùüþ êîíå÷íîãî àâòîìàòà.Äàäèì ñíà÷àëà íåôîðìàëüíîå îïðåäåëåíèå êîíå÷íûõ àâòîìàòîâ è îïèñàíèå èõðàáîòû.øàã ðàáîòûàâòîìàòàÏðîöåññîð: δÑîñòîÿíèå:r2HHÏðîöåññîð: δÑîñòîÿíèå:HHr3 = δ(r2 , s3 )AAñëåäóþùèéøàãAAs1 s2 s3 s4 . . . sks1 s2 s3 s4 . . . skâõîäíàÿ ëåíòàâõîäíàÿ ëåíòàÂõîäíûìè äàííûìè ëþáîãî êîíå÷íîãî àâòîìàòà ÿâëÿþòñÿ ñëîâà â íåêîòîðîì çàðàíåå ôèêñèðîâàííîì àëôàâèòå, âûõîäíûìè äàííûìè ÿâëÿþòñÿ äâå ëîãè÷åñêèå êîíñòàíòû true è false.  êàæäûé ìîìåíò âðåìåíè àâòîìàò íàõîäèòñÿ â îïðåäåë¼ííîì. ×èñëî ñîñòîÿíèé àâòîìàòà êîíå÷íî.

 íà÷àëüíûé ìîìåíòâðåìåíè àâòîìàò íàõîäèòñÿ â. Êðîìå ýòîãî, íåêîòîðûå ñîñòîÿíèÿ àâòîìàòà ñ÷èòàþòñÿ. Âõîäíîå ñëîâî çàïèñûâàåòñÿ íà, ðàçáèòîé íà ÿ÷åéêè: â êàæäîé ÿ÷åéêå ñîäåðæèòñÿ îäíà áóêâà ñëîâà. Àâòîìàòñâÿçàí ñ ëåíòîé ïîñðåäñòâîì ñïåöèàëüíîé, êîòîðàÿ ïîñëåäîâàòåëüíî ñ÷èòûâàåò ñèìâîëû èç ÿ÷ååê, äâèãàÿñü ñëåâà íàïðàâî. Î÷åðåäíîé ñ÷èòàííûéâíóòðåííåì ñîñòîÿíèèòåíà÷àëüíîì ñîñòîÿíèèâûäåëåííûìèóïðàâëÿþùåé ãîëîâêèâõîäíîé ëåí-Ÿ 4. Äåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû13ïðîöåññîðñèìâîë îòïðàâëÿåòñÿ â, êîòîðûé ïî òåêóùåìó ñîñòîÿíèþ è ïî äàííîìóñ÷èòàííîìó ñèìâîëó îïðåäåëÿåò íîâîå ñîñòîÿíèå, â êîòîðîå ïåðåâîäèòñÿ àâòîìàò.Ôóíêöèÿ, âû÷èñëÿþùàÿ ýòî íîâîå ñîñòîÿíèå íàçûâàåòñÿ. Ôóíêöèÿ ïåðåõîäà ðàñïîëîæåíà âíóòðè ïðîöåññîðà è íå èçìåíÿåòñÿ â õîäå âû÷èñëåíèé.Ñ÷èòàâ âñå ñèìâîëû ñëîâà, àâòîìàò îñòàíàâëèâàåòñÿ â îïðåäåë¼ííîì ñîñòîÿíèè: åñëè ýòî ñîñòîÿíèå îêàçûâàåòñÿ âûäåëåííûì, òî íà âûõîä ïîäàåòñÿ êîíñòàíòà true àâòîìàò ðàñïîçíàë ñëîâî, â ïðîòèâíîì ñëó÷àå ïîäàåòñÿ êîíñòàíòà false àâòîìàòíå ðàñïîçíàë ñëîâî.Îòëè÷èòåëüíîé ÷åðòîé êîíå÷íûõ àâòîìàòîâ ÿâëÿåòñÿ îòñóòñòâèå ïàìÿòè âíå ïðîöåññîðà, ò.

å. âñÿ ïàìÿòü àâòîìàòà çàíÿòà ïðîãðàììîé. Ýòà îñîáåííîñòü ïîçâîëÿåòïðîëèòü ñâåò íà ïðè÷èíû íåñïîñîáíîñòè êîíå÷íûõ àâòîìàòîâ ðåøèòü ëþáóþ àëãîðèòìè÷åñêè ðàçðåøèìóþ çàäà÷ó (äëÿ àëãîðèòìîâ îïðåäåë¼ííîãî âèäà íåîáõîäèìàäîïîëíèòåëüíàÿ ïàìÿòü).Òåïåðü ïåðåéäåì ê ôîðìàëüíûì îïðåäåëåíèÿì â òåðìèíàõ òåîðèè ìíîæåñòâ.ôóíêöèåé ïåðåõîäàÄåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì(ñîêðàùåííî ä.ê.à.) íàçûâàåòñÿ óïîðÿäî÷åííàÿ ïÿò¼ðêà A = hQ, A, δ, q0 , F i, ñîñòîÿùàÿ èç ñëåäóþùèõ îáúåêòîâ:Îïðåäåëåíèå.âíóòðåííèõ ñîñòîÿíèé àâòîìàòà;á) A = {a0 , . . . , an } êîíå÷íûé âõîäíîé àëôàâèò àâòîìàòà;â) δ : Q × A → Q ôóíêöèÿ ïåðåõîäà ;ã) q0 ∈ Q íà÷àëüíîå ñîñòîÿíèå ;ä) F ⊆ Q ìíîæåñòâî âûäåëåííûõ (êîíå÷íûõ) ñîñòîÿíèé.à) Q = {q0 , . .

. , qm } êîíå÷íûé àëôàâèòÃðàôè÷åñêîå èçîáðàæåíèå äåòåðìèíèðîâàííûõ àâòîìàòîâÀâòîìàòû óäîáíî èçîáðàæàòü ãðàôè÷åñêè, èñïîëüçóÿ ñëåäóþùèå ãåîìåòðè÷åñêèåôèãóðû:Hd âûäåëåííîå ñîñòîÿíèå;i i íà÷àëüíîå ñîñòîÿíèå;i ïðîìåæóòî÷íîå ñîñòîÿíèå; H id îäíîâðåìåííî íà÷àëüíîå è âûäåëåííîåñîñòîÿíèå;a - i òàêàÿ äóãà ïðèñóòñòâóåò â àâòîìàòå, åñëè çíà÷åíèå ôóíêöèèïåðåõîäà δ(q, a) = q 0 ;qq0i a òàêàÿ ïåòëÿ ïðèñóòñòâóåò â àâòîìàòå, åñëè çíà÷åíèå ôóíêöèèqïåðåõîäà δ(q, a) = q .iÍàïðèìåð, àâòîìàò A = hQ, A, δ, q0 , F i, ãäå A = {a, b}, Q = {q0 , q1 , q2 },F = {q2 }, à ôóíêöèÿ ïåðåõîäà çàäàåòñÿ ñîîòíîøåíèÿìèÏðèìåð.δ(q0 , a) = q0 ,δ(q0 , b) = q1 ,δ(q1 , a) = q0 ,δ(q1 , b) = q2 ,δ(q2 , a) = q2 ,δ(q2 , b) = q2 ,èìååò ñëåäóþùåå ãðàôè÷åñêîå èçîáðàæåíèå:ab?s i b - iHid a, b kq0 a q1q214Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêèÎïðåäåëåíèå.Ïóò¼ì â äåòåðìèíèðîâàííîì êîíå÷íîì àâòîìàòå A = hQ, A, δ, q0, F iíàçîâåì ëþáóþ êîíå÷íóþ ïîñëåäîâàòåëüíîñòü hr0 , s1 , r1 , .

. . , sk , rk i, ãäå r0 , . . . , rk ∈ Q,s1 , . . . , sk ∈ A è δ(ri , si+1 ) = ri+1 äëÿ âñåõ i < k . Åñëè hr0 , s1 , r1 , . . . , sk , rk i ïóòü âàâòîìàòå, òî áóäåì îáîçíà÷àòü åãî ÷åðåçs1s2skr0 −→r1 −→. . . −→rk÷èòàåòñÿ âäîëü äóã äàííîãî ïóòèè ãîâîðèòü, ÷òî ñëîâî w = s1 s2 . . . sk.  ÷àñòíîñòè, ïóñòîå ñëîâî Λ ÷èòàåòñÿ âäîëü ïóòè hr0 i, ñîñòîÿùåãî èç îäíîãî ñîñòîÿíèÿ è íåñîäåðæàùåãî íè îäíîé äóãè.Ïóñòü A = hQ, A, δ, q0 , F i ä.ê.à. Ðàñøèðèì ôóíêöèþ δ äî ôóíêöèèδ : Q × A → Q ñëåäóþùèì îáðàçîì èíäóêöèåé ïî äëèíå ñëîâà:Îïðåäåëåíèå.∗∗δ ∗ (q, Λ) = q,δ ∗ (q, wa) = δ(δ ∗ (q, w), a),ãäå q ∈ Q, w ∈ A∗ , a ∈ A.Îïðåäåëåíèå.Ãîâîðÿò, ÷òî ä.ê.à.

A = hQ, A, δ, q0 , F iðàñïîçíà¼ò ñëîâî w ∈ A∗, åñëèδ ∗ (q0 , w) ∈ F .Äðóãèìè ñëîâàìè, ñëîâî w = s1 s2 . . . sk ðàñïîçíà¼òñÿ àâòîìàòîì, åñëè â í¼ì ñóùåñòâóåò ïóòüs1s2skq0 = r0 −→r1 −→. . . −→rk ∈ Fòàêîé, ÷òî îí íà÷èíàåòñÿ â íà÷àëüíîì ñîñòîÿíèè q0 , âäîëü åãî äóã ÷èòàåòñÿ ñëîâîs1 s2 . . . sk (â äåòåðìèíèðîâàííîì àâòîìàòå òàêîé ïóòü îïðåäåëÿåòñÿ îäíîçíà÷íî ïîñëîâó w) è çàêàí÷èâàåòñÿ â íåêîòîðîì âûäåëåííîì ñîñòîÿíèè.ÿçûê âñåõñëîâ, ðàñïîçíàâàåìûõ êîíå÷íûì àâòîìàòîìßçûê L ⊆ A∗ íàçûâàåòñÿ àâòîìàòíûì, åñëè ñóùåñòâóåò êîíå÷íûéÎïðåäåëåíèå.×åðåç L(A) = {w ∈ A∗ | δ ∗ (q0 , w) ∈ F } áóäåì îáîçíà÷àòüA.Îïðåäåëåíèå.àâòîìàò A òàêîé, ÷òî L = L(A).(ïðîäîëæåíèå). Àâòîìàò èç ïðåäûäóùåãî ïðèìåðà ðàñïîçíà¼ò â òî÷íîñòèâñå ñëîâà â àëôàâèòå {a, b}, êîòîðûå ñîäåðæàò ïîäñëîâî bb, ò.

å. L(A) = {w ∈ {a, b}∗ |w ñîäåðæèò ïîäñëîâî bb}. Äåéñòâèòåëüíî, íà÷àâ ÷òåíèå ïðîèçâîëüíîãî ñëîâà w â íà÷àëüíîì ñîñòîÿíèè äàííîãî àâòîìàòà, ïîïàñòü â âûäåëåííîå ñîñòîÿíèå ìîæíî, òîëüêîïðîéäÿ ïî äóãå, âåäóùåé èç q0 â q1 (ïîìå÷åííîé b), à çàòåì ñðàçó æå ïî äóãå, âåäóùåéèç q1 â q2 (òîæå ïîìå÷åííîé b), òàêîå âîçìîæíî ëèøü â ñëó÷àå, êîãäà w ñîäåðæèòäâå áóêâû b ïîäðÿä.ÏðèìåðŸ 5.Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòûa- iq1a - iq2q ia- iq3Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû îòëè÷àþòñÿîò äåòåðìèíèðîâàííûõ òåì, ÷òî èç ëþáîãî ñîñòîÿíèÿ qïîñëå ñ÷èòûâàíèÿ ñèìâîëà a âîçìîæíû ñðàçó íåñêîëüêî(èëè íè îäíîãî) ïåðåõîäîâ â ñîñòîÿíèÿ, ïðèíàäëåæàùèå∆(q, a).

Ýòî îçíà÷àåò, ÷òî àâòîìàò ìîæåò ïðîäîëæèòü äàëüíåéøèé ïðîöåññìíîæåñòâó âîçìîæíûõ ñîñòîÿíèéŸ 5. Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû15÷òåíèÿ ñèìâîëîâ, ïåðåéäÿ â ëþáîå èç âîçìîæíûõ ñîñòîÿíèé.Ìîæíî ñ÷èòàòü, ÷òî â òàêèõ ñèòóàöèÿõ ðàáîòà àâòîìàòà ðàçâåòâëÿåòñÿ íà íåñêîëüêî ïàðàëëåëüíûõ âåòâåé âû÷èñëåíèé, êàæäàÿ èç êîòîðûõ íà÷èíàåòñÿ ñ îïðåäåëåííîãîñîñòîÿíèÿ qi ∈ ∆(q, a). Åñëè ∆(q, a) ïóñòî, òî ðàáîòà àâòîìàòà âäîëü äàííîé âåòâè âû÷èñëåíèé çàêàí÷èâàåòñÿ â ñîñòîÿíèè q , äàæå åñëè íà âõîäíîé ëåíòå îñòàëèñüíåñ÷èòàííûå ñèìâîëû.