В.Б. Алексеев - Введение в теорию сложности алгоритмов (В.Б. Алексеев - Введение в теорию сложности алгоритмов.pdf), страница 9

. ., â êîòîðûõ ãîëîâêà ïåðåõîäèò÷åðåç ðàçäåëÿþùèå òî÷êè âïðàâî. Ïåðåõîä ãîëîâêè ìàøèíû M ÷åðåçñîîòâåòñòâóþùèå ðàçäåëÿþùèå òî÷êè äåëèò ðàáîòó M íà êàæäîì èç ñëîâā1 |b̄2 , ā1 |ā2 è b̄1 |b̄2 íà ýòàïû. Ìàøèíà M íà ïåðâîì ýòàïå íà ñëîâå ā1 b̄2ðàáîòàåò òàê æå, êàê íà ïåðâîì ýòàïå íà ñëîâå ā1 ā2 . Ïîýòîìó qj1 = qi1è ìàøèíà M íà âòîðîì ýòàïå íà ñëîâå ā1 b̄2 ðàáîòàåò òàê æå, êàê íàâòîðîì ýòàïå íà ñëîâå b̄1 b̄2 .

Îòñþäà qj2 = qi2 è ìàøèíà M íà òðåòüåìýòàïå íà ñëîâå ā1 b̄2 ðàáîòàåò òàê æå, êàê íà òðåòüåì ýòàïå íà ñëîâå ā1 ā2 .Ïðîäîëæàÿ ýòî ðàññóæäåíèå, ìû ïîëó÷àåì óòâåðæäåíèå ëåììû.Îïðåäåëåíèå. Ïóñòü A = {0, 1} è ñëîâî ā = a1 a2 . . . an ∈ A∗ .Áóäåì ãîâîðèòü, ÷òî ñëîâî ā ñèììåòðè÷íî, åñëè a1 = an , a2 = an−1 è ò.ä.Ïóñòü ìàøèíà Òüþðèíãà M èìååò ëåíòî÷íûé àëôàâèò C è ìíîæåñòâîñîñòîÿíèé Q, ïðè÷åì A ⊆ C è q 0 ∈ Q, q 00 ∈ Q.

Áóäåì ãîâîðèòü, ÷òî Mðàñïîçíàåò ñèììåòðèþ, åñëè äëÿ ëþáîãî âõîäíîãî ñëîâà ā ∈ A∗ ìàøèíàM âñåãäà îñòàíàâëèâàåòñÿ è ïðè ýòîì íàõîäèòñÿ â ñîñòîÿíèè q 0 , åñëè āñèììåòðè÷íî, èëè q 00 , åñëè ā íå ñèììåòðè÷íî.Óòâåðæäåíèå. Ñóùåñòâóåò ìàøèíà ÒüþðèíãàM,êîòîðàÿ ðàñ-ïîçíàåò ñèììåòðèþ è äåëàåò ïðè ëþáîì âõîäíîì ñëîâå äëèíû2áîëåå cn øàãîâ, ãäå c íåêîòîðàÿ êîíñòàíòà.níåÄîñòàòî÷íî ïîñòðîèòü ìàøèíó M , êîòîðàÿ çàïîìèíàåò è ñòèðàåò ïåðâûé ñèìâîë, ïåðåãîíÿåò ãîëîâêó â êîíåö ñëîâàè ñðàâíèâàåò ñèìâîë â ïàìÿòè ñ ïîñëåäíèì ñèìâîëîì ñëîâà.

Åñëè îíèíå ñîâïàäàþò, òî M ïåðåõîäèò â ñîñòîÿíèå q 00 è îñòàíàâëèâàåòñÿ. Åñëèñîâïàäàþò, òî îíà ñòèðàåò ïîñëåäíèé ñèìâîë, âîçâðàùàåòñÿ â íà÷àëîñëîâà è ïîâòîðÿåò ïðîöåññ. Åñëè ñëîâî ïîëíîñòüþ ñòåðòî, òî M ïåðåõîäèòâ ñîñòîÿíèå q 0 è îñòàíàâëèâàåòñÿ. Ïðè ýòîì ãîëîâêà íå áîëåå n ðàçïðîáåãàåò ïî ñëîâó äëèíû íå áîëåå n. Ïîýòîìó îáùåå ÷èñëî øàãîâ åñòüO(n2 ).Îïðåäåëåíèå. Ïóñòü S(n) ÷èñëî âñåõ ñèììåòðè÷íûõ äâîè÷íûõñëîâ äëèíû n, à E(n) ÷èñëî âñåõ ñèììåòðè÷íûõ äâîè÷íûõ ñëîâ äëèíûn, óäîâëåòâîðÿþùèõ íåêîòîðîìó çàäàííîìó ñâîéñòâó E . Áóäåì ãîâîðèòü,÷òî ñâîéñòâî E âûïîëíÿåòñÿ äëÿ ïî÷òè âñåõ ñèììåòðè÷íûõ ñëîâ, åñëèlimn→∞ E(n)S(n) = 1.Äîêàçàòåëüñòâî.Ëåììà 4.2.

×èñëî ðàçëè÷íûõ äâîè÷íûõ ñèììåòðè÷íûõ ñëîâ äëènS(n) = 2d 2 e .Ýòî óòâåðæäåíèå ñëåäóåò èç òîãî, ÷òî ñèììåòðè÷íîå ñëîâî îäíîçíà÷íî îïðåäåëÿåòñÿ ñâîåé ïåðâîé ïîëîâèíîé.Òåîðåìà 4.6 (ß. Ì. Áàðçäèíü). Äëÿ ëþáîé ìàøèíû Òüþðèíãà M ,íûnðàâíî39ðàñïîçíàþùåé ñèììåòðèþ, ñóùåñòâóåò êîíñòàíòà cM > 0, òàêàÿ, ÷òî äëÿïî÷òè âñåõ ñèììåòðè÷íûõ ñëîâ X âðåìÿ tM (X) ðàáîòû ìàøèíû M íàñëîâå X óäîâëåòâîðÿåò íåðàâåíñòâó tM (X) > cM |X|2 , ãäå |X| äëèíàñëîâà X .Äîêàçàòåëüñòâî.

Ïóñòü M äàëåå íåêîòîðàÿ ôèêñèðîâàííàÿ ìàøèíà Òüþðèíãà, ðàñïîçíàþùàÿ ñèììåòðèþ äâîè÷íûõ ñëîâ.Ëåììà 4.3. Ïóñòüìåòðè÷íûå ñëîâà èM ðàñïîçíàåò ñèììåòðèþ, ā1 ā2 è b̄1 b̄2 ñèìξM (ā1 |ā2 ) = ξM (b̄1 |b̄2 ). Òîãäà ā1 b̄2 ñèììåòðè÷íîåñëîâî.Òàê êàê M ðàñïîçíàåò ñèììåòðèþ, òî ïðè ðàáîòåíà ñëîâàõ ā1 ā2 è b̄1 b̄2 îíà îñòàíîâèòñÿ â ñîñòîÿíèè q 0 (äà), à ïðè ðàáîòåíà ñëîâå ā1 b̄2 îíà òàêæå îáÿçàòåëüíî îñòàíîâèòñÿ â íåêîòîðîì ñîñòîÿíèè.Íî òîãäà èç ëåììû 4.1 ñëåäóåò, ÷òî è ïðè ðàáîòå íà ñëîâå ā1 b̄2 îíàîñòàíîâèòñÿ â ñîñòîÿíèè q 0 (äà). Òàê êàê M ðàñïîçíàåò ñèììåòðèþ,òî ýòî îçíà÷àåò, ÷òî ā1 b̄2 ñèììåòðè÷íîå ñëîâî.

Ëåììà äîêàçàíà.Îïðåäåëåíèå. Ïóñòü ā = ā1 ā2 è ïóñòü |ā1 | = i (|ā| äëèíàiñëîâà ā). Òîãäà ÷åðåç ξM(ā) áóäåì îáîçíà÷àòü ξM (ā1 |ā2 ). Ïóñòü Q ={q1 , q2 , . . . , qr } ìíîæåñòâî âñåõ ñîñòîÿíèé ìàøèíû M . Ïóñòü 1 6 i 6 nè ξ ∈ Q∗ (ξ ñëîâî â àëôàâèòå Q). ×åðåç An (i, ξ) áóäåì îáîçíà÷àòüìíîæåñòâî âñåõ ñèììåòðè÷íûõ äâîè÷íûõ ñëîâ ā äëèíû n, òàêèõ, ÷òîiξM(ā) = ξ .Äîêàçàòåëüñòâî.Ëåììà 4.4. Äëÿ ëþáîãî i, òàêîãî, ÷òîξ∈Q∗1 6 i 6 b n2 c,è äëÿ ëþáîãîâûïîëíÿåòñÿ íåðàâåíñòâî:n|An (i, ξ)| 6 2d 2 e−i .Ïóñòü ā ∈ An (i, ξ), b̄ ∈ An (i, ξ), ā = ā1 ā2 , b̄ = b̄1 b̄2è |ā1 | = |b̄1 | = i. Òîãäà ñëîâà ā è b̄ ñèììåòðè÷íû è ξM (ā1 |ā2 ) = ξM (b̄1 |b̄2 ).Ïî ëåììå 4.3 îòñþäà ñëåäóåò, ÷òî ñëîâî ā1 b̄2 òîæå ñèììåòðè÷íî.

Ïîñêîëüêó îáà ñëîâà ā1 b̄2 è b̄1 b̄2 ñèììåòðè÷íû è |ā1 | = |b̄1 | 6 b n2 c, òî ā1 = b̄1 .Ñëåäîâàòåëüíî, ó âñåõ ñëîâ èç An (i, ξ) îäèíàêîâîå íà÷àëî äëèíû i. Ïîñêîëüêó ñèììåòðè÷íûå ñëîâà îäíîçíà÷íî îïðåäåëÿþòñÿ ñâîèìè ïåðâûìèd n2 e áóêâàìè, òîÄîêàçàòåëüñòâî.n|An (i, ξ)| 6 2d 2 e−i .Ëåììà 4.5. ÏóñòüQ = {q1 , q2 , . . . , qr } àëôàâèò, â êîòîðîìr > 2.

Òîãäà êîëè÷åñòâî ðàçëè÷íûõ ñëîâ äëèíû íå áîëåå d â àëôàâèòåQ íå ïðåâîñõîäèò rd+1 .23dÄîêàçàòåëüñòâî. ×èñëî òàêèõ ñëîâ ðàâíî r + r + r + · · · + r =rd+1 −rd+1.r−1 < r40Ïóñòü c = const > 0. ×åðåç Anc (i) áóäåì îáîçíà÷àòüìíîæåñòâî âñåõ ñèììåòðè÷íûõ äâîè÷íûõ ñëîâ ā äëèíû n, òàêèõ, ÷òîi(ā)| < bcnc.äëèíà ñëåäà |ξMÎïðåäåëåíèå.Ëåììà 4.6. Åñëè ìàøèíài,òàêîãî, ÷òî16i6M èìååò r ñîñòîÿíèé, òî äëÿ ëþáîãînb 2 c, âûïîëíÿåòñÿ íåðàâåíñòâî:n|Anc (i)| 6 2d 2 e−i+cn log2 r .Èç ëåìì 4.4 è 4.5 ïîëó÷àåìÄîêàçàòåëüñòâî.|Anc (i)| 6nXn|An (i, ξ)| 6 2d 2 e−i · rcn 6 2d 2 e−i+cn log2 r .ξ:|ξ|<bcncÏóñòü c = const > 0. ×åðåç Bcn áóäåì îáîçíà÷àòüìíîæåñòâî âñåõ ñèììåòðè÷íûõ äâîè÷íûõ ñëîâ ā äëèíû n, òàêèõ, ÷òîi(ā)| < bcnc õîòÿ áû äëÿ îäíîãî i òàêîãî, ÷òî b n4 c 6 i 6 b n2 c.|ξMÎïðåäåëåíèå.Ëåììà 4.7.1|Bcn | 6 (n + 12)2n( 4 +c log2 r) .b n4 cÄîêàçàòåëüñòâî.

Ñîãëàñíî ëåììå6 i 6 b n2 c, âûïîëíÿåòñÿ íåðàâåíñòâî:n4.6 äëÿ ëþáîãî i, òàêîãî, ÷òîn|Anc (i)| 6 2d 2 e−b 4 c+cn log2 r .Ïîýòîìónnnn|Bcn | 6 ( − b c + 1)2d 2 e−b 4 c+cn log2 r 624n1n6 ( + 2)2 4 +cn log2 r+2 = (n + 8)2n( 4 +c log2 r) .4Ëåììà 4.8. Ñóùåñòâóåò êîíñòàíòà cM > 0, òàêàÿ, ÷òî|BcnM |= 0.limnn→∞ 2d 2 eÄîêàçàòåëüñòâî.Ñîãëàñíî ëåììå 4.7,|Bcn |n(− 41 +c log2 r)6(n+8)2.n2d 2 eÏîýòîìó óòâåðæäåíèå ëåììû 4.8 áóäåò âûïîëíÿòüñÿ äëÿ ëþáîé êîíñòàíòû c < 4 log1 r .2Ïðîäîëæèì äîêàçàòåëüñòâî òåîðåìû Áàðçäèíÿ. Âûáåðåì äëÿ äàííîé ìàøèíû M êîíñòàíòó cM , óäîâëåòâîðÿþùóþ óñëîâèþ ëåììû 4.8.41Ïóñòü Dcn ìíîæåñòâî âñåõ ñèììåòðè÷íûõ äâîè÷íûõ ñëîâ, íå âõîäÿùèõâ Bcn .

Ïî ëåììàì 4.2 è 4.8 èìååì|DcnM |lim= 1,nn→∞ 2d 2 eïîýòîìó ïî÷òè âñå ñèììåòðè÷íûå äâîè÷íûå ñëîâà âõîäÿò â DcnM . Ïðèýòîì äëÿ ëþáîãî ā ∈ DcnM è ëþáîãî i, òàêîãî, ÷òî b n4 c 6 i 6 b n2 c,i(ā) > bcnc. Òàê êàê âðåìÿ ðàáîòû ìàøèíûâûïîëíÿåòñÿ íåðàâåíñòâî ξMÒüþðèíãà íå ìåíüøå, ÷åì äëèíà âñåõ ñëåäîâ, òî äëÿ âñåõ ñëîâ ā ∈ DcnMèìååì:nncMtM (ā) > (b c − b c)bcM nc >n248ïðè äîñòàòî÷íî áîëüøèõ n. Òåîðåìà 4.6 äîêàçàíà.4.4. Ðåãóëÿðíûå ÿçûêèÐåãóëÿðíûå ÿçûêè ýòî ÿçûêè, ðàñïîçíàâàåìûå àâòîìàòàìè. Âýòîì êîíòåêñòå àâòîìàò ìîæíî îïðåäåëèòü êàê ìàøèíó Òüþðèíãà ñîñëåäóþùèìè îãðàíè÷åíèÿìè: ãîëîâêà ìàøèíû íà êàæäîì øàãå äâèæåòñÿâïðàâî èëè ìàøèíà îñòàíàâëèâàåòñÿ; ìàøèíà îñòàíàâëèâàåòñÿ òîãäà èòîëüêî òîãäà, êîãäà ãîëîâêà îáîçðåâàåò ñèìâîë Λ; ìàøèíà îñòàíàâëèâàåòñÿ â îäíîì èç äâóõ ñîñòîÿíèé q 0 (ïðèíÿòü) èëè q 00 (îòâåðãíóòü).Îïðåäåëåíèå.

Ïóñòü C ëåíòî÷íûé àëôàâèò àâòîìàòà M è A =C\{Λ}. Ïóñòü L ⊆ A∗ . Áóäåì ãîâîðèòü, ÷òî àâòîìàò M ðàñïîçíàåò∗ÿçûê L, åñëè äëÿ ëþáîãî ñëîâà ā ∈ A ðàáîòà M ïðè âõîäíîì ñëîâå ā(â ñòàíäàðòíîé íà÷àëüíîé êîíôèãóðàöèè) çàêàí÷èâàåòñÿ ñîñòîÿíèåì q 0 ,åñëè ā ∈ L, è çàêàí÷èâàåòñÿ ñîñòîÿíèåì q 00 , åñëè ā ∈/ L.Îïðåäåëåíèå. Ïóñòü A íåêîòîðûé àëôàâèò è L ⊆ A∗ íåêîòîðûé ÿçûê â àëôàâèòå A. Äëÿ êàæäîãî ñëîâà ā ∈ A∗ îñòàòî÷íûé ÿçûêLā îïðåäåëèì ñëåäóþùèì îáðàçîìb̄ ∈ Lā ⇐⇒ āb̄ ∈ L.ßçûê íàçûâàåòñÿ ðåãóëÿðíûì, åñëè ó íåãî ëèøü êîíå÷íîå ÷èñëî ðàçëè÷íûõ îñòàòî÷íûõ ÿçûêîâ. (Çäåñü ðàññìàòðèâàåòñÿ è b̄ = Λ ïóñòîå ñëîâî;ïðè ýòîì Λ ∈ Lā ⇐⇒ ā ∈ L). òåîðèè àâòîìàòîâ è ÿçûêîâ äîêàçûâàåòñÿ ñëåäóþùàÿ òåîðåìà(ñì., íàïðèìåð, [11]).Òåîðåìà 4.7.

1) ßçûê, ðàñïîçíàâàåìûé ëþáûì àâòîìàòîì, ðåãóëÿðåí. 2) Äëÿ ëþáîãî ðåãóëÿðíîãî ÿçûêà ñóùåñòâóåò ðàñïîçíàþùèé åãîàâòîìàò.42Ñëåäñòâèå. Åñëè ÿçûêLðåãóëÿðåí, òî äëÿ íåãî ñóùåñòâóåòðàñïîçíàþùàÿ åãî ìàøèíà Òüþðèíãà, âðåìÿ ðàáîòû êîòîðîé (÷èñëîn ðàâíî n + 1.Îêàçûâàåòñÿ, ÷òî íå ñóùåñòâóåò ÿçûêîâ, äëÿ ðàñïîçíàâàíèÿ êîòîðûõ íà ìàøèíàõ Òüþðèíãà äîñòàòî÷íî âðåìåíè ñóùåñòâåííî ìåíüøåãî,÷åì n log2 n (n äëèíà âõîäíîãî ñëîâà) è íå äîñòàòî÷íî âðåìåíè n + 1.Áîëåå òî÷íî ýòî âûðàæàåòñÿ â ïðèâîäèìûõ íèæå òåîðåìàõ.Òåîðåìà 4.8. Ïóñòü ìàøèíà Òüþðèíãà M ðàñïîçíàåò ÿçûê L ⊆∗A è ïóñòü ñóùåñòâóåò êîíñòàíòà c > 0 òàêàÿ, ÷òî ïðè ðàáîòå M∗iíà ëþáîì âõîäíîì ñëîâå ā ∈ A äëèíà ñëåäà ξM (ā) (ñì.

ñòð. 38) íåïðåâîñõîäèò c äëÿ âñåõ 1 6 i 6 n, ãäå n äëèíà ñëîâà ā. Òîãäà L ðåøàãîâ) íà êàæäîì âõîäíîì ñëîâå äëèíûãóëÿðíûé ÿçûê. (Cëåäîâàòåëüíî, ñóùåñòâóåò àâòîìàò, ðàñïîçíàþùèéLñc = 1).Ïóñòü ā ∈ A∗ . Ïîñòðîèì ìíîæåñòâî Dā âñåõñëåäîâ, êîòîðûå ìîãóò ïîëó÷èòüñÿ ïðè ðàáîòå M íà ñëîâàõ âèäà āx̄ ∈ A∗â òî÷êå i, ðàçäåëÿþùåé ā è x̄. Ïóñòü ñëåä qi1 qi2 qi3 . .

. qis ∈ Dā . Ðàññìîòðèìðàáîòó ìàøèíû M ñëåâà îò ðàçäåëÿþùåé òî÷êè. Îíà îäíîçíà÷íî îïðåäåëÿåòñÿ ñëîâîì ā è òåìè ñîñòîÿíèÿìè qi2 , qi4 , . . . , â êîòîðûõ íàõîäèòñÿìàøèíà, êîãäà ãîëîâêà âîçâðàùàåòñÿ íà ëåâóþ çîíó ÷åðåç òî÷êó i. Ïîóñëîâèþ s 6 c. Åñëè s ÷åòíî, òî ìàøèíà îñòàíàâëèâàåòñÿ ñëåâà îò òî÷êèi.  ýòîì ñëó÷àå ê ïîñëåäîâàòåëüíîñòè qi1 qi2 qi3 ïðèïèøåì +, åñëè Mîñòàíàâëèâàåòñÿ â ñîñòîÿíèè ïðèíÿòü, è ïðèïèøåì −, åñëè M îñòàíàâëèâàåòñÿ â ñîñòîÿíèè îòâåðãíóòü. Òàê êàê s 6 c, òî âîçìîæíûõ ñëåäîâêîíå÷íîå ÷èñëî è ðàçíûõ âîçìîæíûõ ìíîæåñòâ Dā òàêæå êîíå÷íîå ÷èñëî.Òîãäà óòâåðæäåíèå òåîðåìû 4.8 âûòåêàåò èç ñëåäóþùåé ëåììû.Äîêàçàòåëüñòâî.Ëåììà 4.9.

ÅñëèDā = Db̄ ,òî îñòàòî÷íûå ÿçûêèLāèLb̄ñîâïà-äàþò.Ïóñòü x̄ ëþáîå ñëîâî èç A∗ . Ðàññìîòðèì ðàáîòóM íà ñëîâàõ āx̄ è b̄x̄. Ïóñòü qi1 qi2 qi3 . . . qis è qj1 qj2 . . . qjm ñëåäû â òî÷êàõ,ðàçäåëÿþùèõ ā è x̄, b̄ è x̄. Çàìåòèì, ÷òî ðàáîòà ñïðàâà îò ðàçäåëÿþùèõòî÷åê îäíîçíà÷íî îïðåäåëÿåòñÿ ñëîâîì x̄ è ñîñòîÿíèÿìè qi1 qi3 qi5 . .

. èqj1 qj3 qj5 . . ., â êîòîðûõ ãîëîâêà ïåðåõîäèò ÷åðåç ðàçäåëÿþùèå òî÷êè âïðàâî. Ïðè ýòîì qi1 è qj1 îäíîçíà÷íî îïðåäåëÿþòñÿ ïî ā è b̄. Òàê êàê Dā = Db̄ ,òî qi1 = qj1 è ðàáîòà ñïðàâà ïîñëå ïåðâîãî ïåðåõîäà ÷åðåç ðàçäåëÿþùèåòî÷êè ïðîèñõîäèò îäèíàêîâî. Òîãäà qi2 = qj2 . Îïÿòü, òàê êàê Dā = Db̄ , òîqi3 = qj3 è îïÿòü ðàáîòà ñïðàâà ïðîèñõîäèò îäèíàêîâî. Ïîñëåäîâàòåëüíîïîëó÷àåì, ÷òî s = m è qir = qjr äëÿ âñåõ r = 1, 2, . . . , s. Åñëè s íå÷åòíî,òî ïîñëå ïåðåõîäà âïðàâî â ñîñòîÿíèè qis â îáîèõ ñëó÷àÿõ ðàáîòà ñïðàâàáóäåò îäèíàêîâîé è, ñëåäîâàòåëüíî, M îñòàíîâèòñÿ â îäíîì è òîì æåÄîêàçàòåëüñòâî.43ñîñòîÿíèè.