С.С. Марченков - Избранные главы дискретной математики (1124120), страница 26
Текст из файла (страница 26)
. ais . Òîãäà ñîîòâåòñòâóþùèì ðåãóëÿðíûì âûðàæåíèåìáóäåò âûðàæåíèå(a1 ∪ a2 )∗ · ai1 · . . . · ais · (a1 ∪ a2 )∗ .e) Áóäåì ñ÷èòàòü, ÷òî ñëîâî ā íåïóñòî (â ïðîòèâíîì ñëó÷àå ðåøåíèåìçàäà÷è ÿâëÿåòñÿ ïóñòîå ìíîæåñòâî ∅). Ïîñêîëüêó â îáùåì ñëó÷àå ðåøåíèå çàäà÷è äîâîëüíî ãðîìîçäêî, ðàññìîòðèì äâà ÷àñòíûõ ñëó÷àÿ. Ïóñòüā = a1 . Òîãäà ìíîæåñòâî âñåõ ñëîâ, íå ñîäåðæàùèõ áóêâû a1 , ýòî ìíîæåñòâî âñåõ ñëîâ, ñîñòîÿùèõ òîëüêî èç áóêâû a2 (âêëþ÷àÿ ïóñòîå ñëîâî). Ñîîòâåòñòâóþùåå ðåãóëÿðíîå âûðàæåíèå èìååò âèä a∗2 . Ïóñòü òåïåðüā = a1 a1 a2 . Òîãäà ïðîèçâîëüíîå ñëîâî, íå ñîäåðæàùåå ïîäñëîâî a1 a1 a2 ,èìååò âèälak21 a1 al21 a1 al22 .
. . a1 a2p ak12 ,ãäå k1 , k2 , p ïðîèçâîëüíûå íåîòðèöèàòåëüíûå, à l1 , . . . , lp ïðîèçâîëüíûå íàòóðàëüíûå ÷èñëà. Èç ýòîãî ïðåäñòàâëåíèÿ ñëåäóåò âèä ðåãóëÿðíîãî âûðàæåíèÿ, ðåøàþùåãî ïîñòàâëåííóþ çàäà÷ó: a∗2 · (a1 · a∗2 · a2 )∗ · a∗1 .Îòìåòèì åù¼, ÷òî äëÿ ïðîèçâîëüíîãî ñëîâà ā çàäà÷ó ïðîùå ðåøèòü, åñëè ñíà÷àëà îïðåäåëèòü äåòåðìèíèðîâàííûé àâòîìàò, êîòîðûé äîïóñêàåòìíîæåñòâî âñåõ ñëîâ, ñîäåðæàùèõ â êà÷åñòâå ïîäñëîâà ñëîâî ā.
Çàòåìñëåäóåò ïåðåéòè ê äîïîëíåíèþ ýòîãî ìíîæåñòâà è âîñïîëüçîâàòüñÿ òåîðåìîé Êëèíè.11. Íåîáõîäèìî âîñïîëüçîâàòüñÿ òåì æå ïðè¼ìîì, ÷òî è ïðè äîêàçàòåëüñòâå âòîðîé ÷àñòè òåîðåìû Êëèíè. Îòëè÷èå â äîêàçàòåëüñòâå áóäåòñîñòîÿòü â òîì, ÷òî ïåðåõîä èç îäíîãî ñîñòîÿíèÿ â íåïîñðåäñòâåííî ñëåäóþùåå ñîñòîÿíèå îñóùåñòâëÿåòñÿ ïîä äåéñòâèåì ñëîâà, êîòîðîå, âîîáùåãîâîðÿ, íå ÿâëÿåòñÿ áóêâîé âõîäíîãî àëôàâèòà.12. Íåîáõîäèìî ïðèìåíèòü òåîðåìó Êëèíè.
Åñëè ðåãóëÿðíîå âûðàæåíèå α íàä àëôàâèòîì A îïðåäåëÿåò êîíå÷íî-àâòîìàòíîå ìíîæåñòâîX , à ðåãóëÿðíûå âûðàæåíèÿ β1 , . . . , βk íàä àëôàâèòîì B êîíå÷íîàâòîìàòíûå ìíîæåñòâà Y1 , . . . , Yk , òî, êàê íåòðóäíî çàìåòèòü, ìíîæåñòâî X[Y1 , . . . , Yk ] áóäåò îïðåäåëÿòüñÿ ðåãóëÿðíûì âûðàæåíèåì, êîòîðîå123ïîîëó÷àåòñÿ èç ðåãóëÿðíîãî âûðàæåíèÿ α çàìåíîé ñèìâîëîâ a1 , . . . , ak ñîîòâåòñòâåííî ðåãóëÿðíûìè âûðàæåíèÿìè β1 , .
. . , βk . Çíà÷èò, ìíîæåñòâîX[Y1 , . . . , Yk ] òàêæå êîíå÷íî-àâòîìàòíî.13. Ñëåäóåò âîñïîëüçîâàòüñÿ ðåãóëÿðíûìè âûðàæåíèÿìè. Èç îïåðàöèé îáúåäèíåíèÿ, ïðîèçâåäåíèÿ è èòåðàöèè íà ïîðÿäîê áóêâ â ñëîâàõâëèÿíèå îêàçûâàåò òîëüêî îïåðàöèÿ ïðîèçâåäåíèÿ. Ïîýòîìó åñëè ðåãóëÿðíîå âûðàæåíèå α îïðåäåëÿåò êîíå÷íî-àâòîìàòíîå ìíîæåñòâî X , òîîáðàùåíèå ìíîæåñòâà X áóäåò îïðåäåëÿòüñÿ ðåãóëÿðíûì âûðàæåíèåì β ,êîòîðîå ïîëó÷àåòñÿ èç α îäíîâðåìåííîé ïåðåñòàíîâêîé âñåõ ñîìíîæèòåëåé â ïðîèçâåäåíèÿõ. Èíà÷å ãîâîðÿ, ðåãóëÿðíîå âûðàæåíèå β íåîáõîäèìîîïðåäåëèòü ïàðàëëåëüíî èíäóêòèâíîìó îïðåäåëåíèþ âûðàæåíèÿ α. Ïðèýòîì ïï. 13 â îïðåäåëåíèè ðåãóëÿðíîãî âûðàæåíèÿ α ïåðåíîñÿòñÿ áåçèçìåíåíèÿ è íà âûðàæåíèå β , à â ï.
4 ïðè ïåðåõîäå îò α ê β íåîáõîäèìîâ ïðîèçâåäåíèè ïîìåíÿòü ïîðÿäîê ñîìíîæèòåëåé.Ãëàâà 3.1.0, 0∗1, 0q1q20, 00, 11, 01, 1q40, 1q31, 1Âåñ ðàâåí 4.3. 1),3) äà, 2),4),5) íåò.4. 1) 3 îñòàòî÷íûå ôóíêöèè, êîòîðûå îòâå÷àþò âõîäíûì ñëîâàì Λ, 0, 1;2) 2 îñòàòî÷íûå ôóíêöèè, êîòîðûå îòâå÷àþò âõîäíûì ñëîâàì Λ, 0; 3) áåñêîíå÷íîå ÷èñëî îñòàòî÷íûõ ôóíêöèé, êàæäàÿ èç êîòîðûõ îïðåäåëÿåòñÿ,íàïðèìåð, ñëîâîì 0n , (n > 0).5.
1) âåñ ðàâåí 2, 2) âåñ ðàâåí 4, 3) âåñ ðàâåí 3, 4) âåñ ðàâåí 2.2.1246.1)y1 (t) = q̄1 (t − 1),q1 (t) = q1 (t − 1) → q2 (t − 1),q (t) = x̄(t), 2q1 (0) = q2 (0) = 0,âåñ ñóïåðïîçèöèè ðàâåí 3. 2) Âåñ ðàâåí 5.3)y(t) = q1 (t − 1),q1 (t) = x̄(t) · q2 (t − 1) ∨ q1 (t − 1),q (t) = x(t), 2q1 (0) = 0, q2 (0) = 1,âåñ ñóïåðïîçèöèè ðàâåí 2.7. 1) y(t) = x2 (t),q(t) = 1,q(0) = 0,âåñ ïîëó÷åííîé ôóíêöèè ðàâåí 1.2á)y(t) = 1,q1 (t) = q1 (t − 1) ⊕ q2 (t − 1),q (t) = x1 (t) ⊕ q1 (t − 1), 2q1 (0) = q2 (0) = 0,âåñ ïîëó÷åííîé ôóíêöèè ðàâåí 1.8.
Ïîäîáíûå çàäà÷è òðàäèöèîííî ðåøàþòñÿ ñ ïîìîùüþ ïîñòðîåíèÿñõåì, ñîñòîÿùèõ èç àâòîìàòíûõ ýëåìåíòîâ. Òàê æå, êàê äëÿ ñõåì èçôóíêöèîíàëüíûõ ýëåìåíòîâ, ñòðîèòñÿ îðèåíòèðîâàííûé ãðàô ñ âõîäíûìè ïîëþñàìè (âåðøèíû, ñîîòâåòñòâóþùèå âõîäíûì ïåðåìåííûì x), âûõîäíûìè ïîëþñàìè (âåðøèíû, ñîîòâåòñòâóþùèå âûõîäíûì ïåðåìåííûìy ) è âåðøèíàìè, ñîîòâåòñòâóþùèìè àâòîìàòíûì ýëåìåíòàì f∨ , f& , f− , ç(íèæå â ñõåìå ìû îñòàâëÿåì òîëüêî ñèìâîëû ∨, &, , ç).  ãðàôå äîïóñêàþòñÿ îðèåíòèðîâàííûå öèêëû, êîòîðûå îáÿçàòåëüíî äîëæíû ïðîõîäèòü ÷åðåç ýëåìåíòû çàäåðæêè. Ñ èñïîëüçîâàíèåì ýòèõ ñõåì íåòðóäíîâîññòàíîâèòü ïîñëåäîâàòåëüíîñòü ïðèìåíåíèÿ îïåðàöèé ñóïåðïîçèöèè èââåäåíèÿ îáðàòíîé ñâÿçè, ïðèâîäÿùóþ â èòîãå ê ïîñòðîåíèþ èñêîìûõôóíêöèé íà îñíîâå çàäàííûõ àâòîìàòíûõ ôóíêöèé.  ïðèâîäèìûõ äàëåå äâóõ ñõåìàõ ïðÿìîóãîëüíèêàìè âûäåëåíû ÷àñòè ñõåì, êîòîðûå íå125q0xx1x2q10q20∨·∨∨z···∨∨∨yy1y2zzñîäåðæàò ýëåìåíòîâ çàäåðæêè è êîòîðûå îïðåäåëÿþò òîëüêî èñòèííîñòíûå ôóíêöèè.9.
 îáîèõ ñëó÷àÿõ ñóïåðïîçèöèÿìè ôóíêöèè f1 ìîæíî ïîëó÷èòü âñåèñòèííîñòíûå ôóíêöèè èç êëàññà P ,2 . Äàëåå ïîäñòàíîâêîé èñòèííîñòíûõ ôóíêöèé-êîíñòàíò â ôóíêöèþ f2 îáðàçóåì åäèíè÷íóþ çàäåðæêó.êàÃëàâà 4.Ïóñòü ïðîãðàììà ìàøèíû Òüþðèíãà M ñîäåðæèò êîìàíäó (4.1),ãäå D = S . Äîáàâèì ê ìíîæåñòâó ñîñòîÿíèé ìàøèíû M íîâîå ñîñòîÿíèåqs0 , à êîìàíäó (4.1) çàìåíèì ñåðèåé èç k + 2 êîìàíä1.ai qj → al Lqs0 ,am qs0 → am Rqs (l = 0, 1, . . .
, k).Ïðîäåëàâ ýòî ïðåîáðàçîâàíèå ñî âñåìè êîìàíäàìè ìàøèíû M, ñîäåðæàùèìè ñèìâîë S , ïîëó÷èì ïðîãðàììó ìàøèíû Òüþðèíãà M0 , êîòîðàÿýêâèâàëåíòíà ìàøèíå M.2. Ìîæíî ðåàëèçîâàòü ñëåäóþùèé àëãîðèòì âû÷èñëåíèÿ: ñòåðåòü ïåðâóþ åäèíèöó îñíîâíîãî êîäà, ïðîáåæàòü ñëåâà íàïðàâî îñòàâøèéñÿ ìàññèâ èç åäèíèö (åñëè îí åñòü), çàìåíèòü ðàçäåëèòåëüíûé íóëü åäèíèöåé,âåðíóòüñÿ ê íà÷àëó ïîëó÷åííîãî ìàññèâà èç åäèíèö, ñòåðåòü â íåì ïåðâóþåäèíèöó, ñäâèíóòüñÿ âïðàâî íà îäíó êëåòêó è îñòàíîâèòüñÿ.3. Ìîæåò, òîëüêî ýòè ôóíêöèè äîëæíû çàâèñåòü îò ðàçëè÷íîãî ÷èñëàïåðåìåííûõ. Îäíà èç ïðîñòåéøèõ ìàøèí òàêîãî òèïà ïðàâèëüíî âû÷èñëÿåò ôóíêöèè x + 1 è x + y + 2.
Äëÿ ýòîãî îíà ïðîáåãàåò ñëåâà íàïðàâîïåðâûé ìàññèâ èç åäèíèö, çàìåíÿåò ñòîÿùèé ñïðàâà 0 íà 1 è çàòåì âîçâðàùàåòñÿ íà ïåðâóþ åäèíèöó âíîâü îáðàçîâàâøåãîñÿ ìàññèâà.04. Ìîæíî. Äîñòàòî÷íî äëÿ ìàøèíû M ïîìåíÿòü ðîëÿìè ¾ëåâî¿ è126¾ïðàâî¿. Èíûìè ñëîâàìè, îñíîâíîé êîä íàáîðà (x1 , . . . , xn ) ñëåäóåò ïðåîáðàçîâàòü â îñíîâíîé êîä íàáîðà (xn , . . . , x1 ), à â íà÷àëüíûé ìîìåíòâðåìåíè ãîëîâêó ìàøèíû M0 óñòàíîâèòü íà ñàìóþ ïðàâóþ åäèíèöó îñíîâíîãî êîäà.6.
Ñíà÷àëà ñëåäóåò çàïèñàòü ñèìâîë 1 ñëåâà èëè ñïðàâà îò îñíîâíîãîêîäà, îòñòóïèâ íà îäíó ïóñòóþ êëåòêó. Çàòåì (ýòè äåéñòâèÿ áóäóò öèêëè÷åñêè ïîâòîðÿòüñÿ) íåîáõîäèìî â îñíîâíîì êîäå ÷èñëà x çàìåíèòü äâåêðàéíèå åäèíèöû íóëÿìè (ñîáëþäàéòå îñòîðîæíîñòü: îíè ìîãóò îêàçàòüñÿ ïîñëåäíèìè), äîáàâèòü åäèíèöó ê ðàíåå ïîñòàâëåííîé åäèíèöå è ò.ä.7. Äëÿ ñëó÷àÿ l = 3 ïðîãðàììà ìàøèíû M6 âûãëÿäèò òàê:q1q20 0Rq2 0Rq21 1Rq1 1Rq3q3q4q5q6q61q620Lq7 0Lq5 1Lq61 1Lq62 1Sq11Lq4 0Lq5 1Lq6 1Lq6q7q8q9q91q9200Lq8 1Lq91 1Lq92 1Sq01 0Lq8 1Lq9 1Lq9Äâîéíûìè âåðòèêàëüíûìè îòðåçêàìè îòäåëåíû ÷àñòè ìàøèíû M6 , êîòîðûå ìîæíî ðàññìàòðèâàòü êàê ñàìîñòîÿòåëüíûå ìàøèíû Òüþðèíãà.9.
Äëÿ âñÿêîé ìàøèíû Òüþðèíãà M ìîæíî ïîñòðîèòü ýêâèâàëåíòíóþìàøèíó Òüþðèíãà, åñëè äîïèñàòü ê ïðîãðàììå ìàøèíû M ïðîèçâîëüíóþ ¾ôèêòèâíóþ¿ ÷àñòü (ñîñòîÿíèÿ è êîìàíäû, êîòîðûå íå ñâÿçàíû ññîñòîÿíèÿìè ìàøèíû M).10. Ïóñòü ôóíêöèÿ U (x, 2x) èìååò âñþäó îïðåäåëåííîå âû÷èñëèìîåäîîïðåäåëåíèå V (x). Òîãäà ôóíêöèÿ V (x) + 1 òàêæå âñþäó îïðåäåëåíà èâû÷èñëèìàà. Âîçüìåì òàêîå n, ÷òîáû âû÷èñëèìàÿ ôóíêöèÿ U (n, 2x) êàêôóíêöèÿ îò x ñîâïàäàëà ñ ôóíêöèåé V (x) + 1, ò.å. U (n, 2x) = V (x) + 1.Ïîëó÷èì ïðîòèâîðå÷èå, åñëè ïîëîæèì x = n.11.
Ïóñòü ôóíêöèÿ U (n, x) âû÷èñëèìà íà ìàøèíå Òüþðèíãà U , àôóíêöèÿ U (n0 , x) îïðåäåëåíà õîòÿ áû â îäíîé òî÷êå. Ðàññìîòðèì àëãîðèòì âû÷èñëåíèÿ âñþäó îïðåäåëåííîé ôóíêöèè f (n, x, t), êîòîðàÿ ïåðå÷èñëÿåò ìíîæåñòâî M . Çàïóñêàåì ìàøèíó U íà ïàðå (n, x) è ¾ïðîñëåæèâàåì¿ âû÷èñëåíèå â òå÷åíèå t òàêòîâ. Åñëè ìàøèíà U çà ýòî âðåìÿçàêàí÷èâàåò âû÷èñëåíèå, òî ïîëàãàåì f (n, x, t) = n.  ïðîòèâíîì ñëó÷àåïîëàãàåì f (n, x, t) = n0 .k12. 1. Ïóñòü p(x) = ak x + .
. . + a1 x + a0 , ãäå k > 1, ak 6= 0, èa = max{ak , . . . , a1 , a0 }. Òîãäà âîçìîæíîå ðåøåíèå óðàâíåíèÿ y = p(x)127çàêëþ÷åíî â ïðåäåëàõrky6x6a(k + 1)rky.akÑëåäîâàòåëüíî, äëèíà |x| äâîè÷íîé çàïèñè ÷èñëà x áóäåò íàõîäèòüñÿ âïðåäåëàõ[(|y| − |a(k + 1)| − 1)/k] 6 |x| 6 d(|y| − |ak | + 1)/k)e.Èç ýòîé ôîðìóëû âèäíî, ÷òî èíòåðâàë äëÿ âîçìîæíûõ çíà÷åíèé âåëè÷èíû |x| èìååò êîíñòàíòíóþ äëèíó (çàâèñÿùóþ òîëüêî îò ïîëèíîìà p). Äëÿñîîòâåòñòâóþùèõ çíà÷åíèé ïåðåìåííîé x íåîáõîäèìî âû÷èñëèòü çíà÷åíèÿ ïîëèíîìà p è ñðàâíèòü èõ ñî çíà÷åíèåì y . Ýòî ïðèâîäèò ê ïîëèíîìèàëüíîìó ïåðåáîðíîìó àëãîðèòìó.2.
Ðåøåíèå ýòîé çàäà÷è ñâîäèòñÿ ê ðåøåíèþ çàäà÷è èç ï.1.3. Äëÿ îòûñêàíèÿ ðåøåíèÿ óðàâíåíèÿ y = cx ñëåäóò, íàïðèìåð, ïåðåáðàòüâñå çíà÷åíèÿ x, íå ïðåâîñõîäÿùèå [log2 y/ log2 c] 6 |y|+1, è ïðîâåðèòü âûïîëíåíèå ðàâåíñòâà y = cx . Ïîñêîëüêó êàæäîå óìíîæåíèå íà êîíñòàíòó câûïîëíÿåòñÿ çà íå áîëåå ÷åì êâàäðàòè÷íîå (îò äëèíû çàïèñè àðãóìåíòà)âðåìÿ, ïðèõîäèì ê ïîëèíîìèàëüíîìó âðåìåíè ðåøåíèÿ äàííîé çàäà÷è.4. Íåîáõîäèìî ïðåäâàðèòåëüíî ïðèâåñòè êâàäðàòíóþ ìàòðèöó ê äèàãîíàëüíîìó âèäó.13. 1. Íåîáõîäèìî ñíà÷àëà âûäåëèòü ñóùåñòâåííûå ïåðåìåííûå ôóíêöèè, à çàòåì âîñïîëüçîâàòüñÿ òåì ôàêòîì, ÷òî ëèíåéíàÿ ôóíêöèÿ ðàâíà1 íà íàáîðàõ (äëÿ ñóùåñòâåííûõ ïåðåìåííûõ) ëèáî òîëüêî ñ íå÷åòíûì,ëèáî òîëüêî ñ ÷åòíûì ÷èñëîì åäèíèö.2.
 ñëó÷àå çàäàíèÿ òàáëèöåé çíà÷åíèé ìîæíî âïðÿìóþ âîñïîëüçîâàòüñÿ îïðåäåëåíèåì ìîíîòîííîé ôóíêöèè.  ñëó÷àå ïîëèíîìà Æåãàëêèíàíåîáõîäèìî ïðèìåíèòü ñëåäóþùåå óòâåðæäåíèå: ôóíêöèÿ F (x1 , . . . , xn )ìîíîòîííà òîãäà è òîëüêî òîãäà, êîãäà ïðè ëþáîì i (1 6 i 6 n) ñïðàâåäëèâî òîæäåñòâîf (x1 , . . . , xi−1 , 0, xi+1 . . . , xn ) · (f (x1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
