PDF-лекции (1121253), страница 8
Текст из файла (страница 8)
w L@BOM SLU^AE f (i) =6 'i(i) | PROTIWORE^IE.sLEDOWATELXNO (OT PROTIWNOGO) ti(i) > T (i). tEOREMA DOKAZANA.tEOREMA. dLQ L@BOJ OB]EREKURSIWNOJ FUNKCII T (x) SU]ESTWUET OB]EREKURSIWNAQ FUNKCIQ f (x) PRINIMA@]AQ TOLXKO ZNA^ENIQI I TAKAQ ^TO DLQ L@BOJ MA[INY tX@RINGA Mi WY^ISLQ@]EJ f (x)SU]ESTWUET BESKONE^NOE ^ISLO ZNA^ENIJ x DLQ KOTORYH WYPOLNQETSQNERAWENSTWO ti (x) > T (x)dOKAZATELXSTWO pUSTX g(x) = x ; (bpxc)2. tOGDA FUNKCIQ g(x) WY^ISLIMA I WS@DU OPREDELENA (TO ESTX OB]EREKURSIWNA). pRI x = 0; 1; 2; 3; : : : FUNKCIQ g(x) PRINIMAET ZNA^ENIQ.|,,-..-,12,,,..390,0; 0; 1; 2; 0; 1; 2; 3; 4; 0; 1; : : : . lEGKO DOKAZATX, ^TO FUNKCIQ g(x) PRINIMAET KAVDOE ZNA^ENIE IZ Z + BESKONE^NOE ^ISLO RAZ.
oPREDELIM FUNKCI@f (x) SLEDU@]IM OBRAZOM:(f (x) = 1; ESLI tg(x)(x) 6 T (x) I 'g(x) (x) = 0;(13)0; INA^E:tOGDA FUNKCIQ f (x) OB]EREKURSIWNA (DOKAZYWAETSQ TAK VE, KAKW PREDYDU]EJ TEOREME). pUSTX MA[INA Mi WY^ISLQET f (x), TO ESTXf (x) = 'i(x). pUSTX j - L@BOE ^ISLO, TAKOE, ^TO g(j ) = i (TAKIH jBESKONE^NO MNOGO). dOPUSTIM, ^TO ti (j ) 6 T (j ). tOGDA PO OPREDELENI@f (x) POLU^AEM: ESLI 'i (j ) = 0, TO f (j ) = 1, A ESLI 'i (j ) 6= 0 , TOf (j ) = 0. w L@BOM SLU^AE f (j ) 6= 'i (j ) - PROTIWORE^IE. sLEDOWATELXNO,ti(j ) > T (j ).
tEOREMA DOKAZANA.sPRAWEDLIWO E]E BOLEE SILXNOE UTWERVDENIE, KOTOROE MY PRIWEDEM BEZ DOKAZATELXSTWA.tEOREMA. dLQ L@BOJ OB]EREKURSIWNOJ FUNKCII T (x) SU]ESTWUET OB]EREKURSIWNAQ FUNKCIQ f (x) PRINIMA@]AQ TOLXKO ZNA^ENIQI I TAKAQ ^TO DLQ L@BOJ MA[INY tX@RINGA Mi WY^ISLQ@]EJf (x) MNOVESTWO TEH x DLQ KOTORYH ti(x) 6 T (x) KONE^NOtEOREMY POKAZYWA@T, ^TO SU]ESTWU@T SKOLX UGODNO SLOVNO WY^ISLIMYE OB]EREKURSIWNYE FUNKCII S DWUMQ ZNA^ENIQMI (ILI, ^TO\KWIWALENTNO, SKOLX UGODNO SLOVNO RASPOZNAWAEMYE QZYKI). wOZNIKAETWOPROS: A KAKOJ WOOB]E MOVET BYTX SLOVNOSTX ZADA^ (QZYKOW)? sU]ESTWENNYJ OTWET NA \TOT WOPROS DAET SLEDU@]AQ TEOREMA, KOTORU@MY PRIWODIM BEZ DOKAZATELXSTWA.tEOREMA. pUSTX OB]EREKURSIWNYE FUNKCII t(n) I T (n) TAKOWYT(n)^TO t(n) log2 t(n) ! 1 PRI n ! 1 tOGDA SU]ESTWUET QZYK L KOTORYJ RASPOZNAETSQ NEKOTOROJ MA[INOJ tX@RINGA S ^ISLOM [AGOW NEBOLEE T (n) DLQ WSEH WHODNYH SLOW L@BOJ DLINY n I NE RASPOZNAETSQNIKAKOJ MA[INOJ tX@RINGA S ^ISLOM [AGOW t(n)|TA TEOREMA POKAZYWAET, ^TO WOZMOVNYE FUNKCII SLOVNOSTIQZYKOW OBRAZU@T DOWOLXNO PLOTNOE MNOVESTWO.
mOVNO LI POLU^ITXREZULXTAT O BOLX[EJ PLOTNOSTI W OB]EM SLU^AE NEIZWESTNO. oDNAKODLQ ODNOGO WAVNOGO INTERWALA MY SEJ^AS POLU^IM OTRICATELXNYJ OTWET. a IMENNO, MY POKAVEM, ^TO NE SU]ESTWUET QZYKOW SO SLOVNOSTX@RASPOZNAWANIQ PO PORQDKU MEVDU n I n log n.-,012,,,,,.,.,().40-rEGULQRNYE QZYKIrEGULQRNYE QZYKI | \TO QZYKI, RASPOZNAWAEMYE AWTOMATAMI. w\TOM KONTEKSTE AWTOMAT MOVNO OPREDELITX KAK MA[INU tX@RINGA SOSLEDU@]IMI OGRANI^ENIQMI: GOLOWKA MA[INY NA KAVDOM [AGE DWIVETSQ WPRAWO ILI MA[INA OSTANAWLIWAETSQ; MA[INA OSTANAWLIWAETSQTOGDA I TOLXKO TOGDA, KOGDA GOLOWKA OBOZREWAET SIMWOL ; MA[INAOSTANAWLIWAETSQ W ODNOM IZ DWUH SOSTOQNIJ q0 ("PRINQTX") ILI q00("OTWERGNUTX").oPREDELENIE. pUSTXC - LENTO^NYJ ALFAWIT AWTOMATA M I A =C nfg.
pUSTX L A . bUDEM GOWORITX, ^TO AWTOMAT M RASPOZNAETQZYK L, ESLI DLQ L@BOGO SLOWA a 2 A RABOTA M PRI WHODNOM SLOWEa (W STANDARTNOJ NA^ALXNOJ KONFIGURACII) ZAKAN^IWAETSQ SOSTOQNIEMq0, ESLI a 2 L, I ZAKAN^IWAETSQ SOSTOQNIEM q00 , ESLI a 2= L.oPREDELENIE. pUSTX A - NEKOTORYJ ALFAWITI L A - NEKOTORYJ QZYK W ALFAWITE A. dLQ KAVDOGO SLOWA a 2 A OSTATO^NYJ QZYKLb OPREDELIM SLEDU@]IM OBRAZOMb 2 La () ab 2 L:qZYK NAZYWAETSQ REGULQRNYM, ESLI U NEGO LI[X KONE^NOE ^ISLO RAZLI^NYH OSTATO^NYH QZYKOW. (zDESX RASSMATRIWAETSQ I b = | PUSTOESLOWO; PRI \TOM 2 La () a 2 L).w TEORII AWTOMATOW I QZYKOW DOKAZYWAETSQ SLEDU@]AQ TEOREMA(SM., NAPRIMER, [ ]).tEOREMA. qZYK RASPOZNAWAEMYJ L@BYM AWTOMATOM REGULQREN dLQ L@BOGO REGULQRNOGO QZYKA SU]ESTWUET RASPOZNA@]IJ EGOAWTOMATsLEDSTWIE.
eSLI QZYK L REGULQREN TO DLQ NEGO SU]ESTWUETRASPOZNA@]AQ EGO MA[INA tX@RINGA WREMQ RABOTY KOTOROJ ^ISLO[AGOW NA KAVDOM WHODNOM SLOWE DLINY n RAWNO n + 1oKAZYWAETSQ, ^TO NE SU]ESTWUET QZYKOW, DLQ RASPOZNAWANIQ KOTORYH NA MA[INAH tX@RINGA DOSTATO^NO WREMENI SU]ESTWENNO MENX[EGO, ^EM n log2 n (n - DLINA WHODNOGO SLOWA) I NE DOSTATO^NO WREMENIn + 1. bOLEE TO^NO \TO WYRAVAETSQ W PRIWODIMYH NIVE TEOREMAH.oPREDELENIE. rASSMOTRIM TO^KU NA LENTE MA[INY tX@RINGAMEVDU Q^EJKAMI S NOMERAMI i I i + 1. sLEDOM W \TOJ TO^KE PRI RABOTEMA[INY NA NEKOTOROM WHODNOM SLOWE BUDEM NAZYWATX POSLEDOWATELXNOSTX WSEH SOSTOQNIJ, W KOTORYE PEREHODIT MA[INA, KOGDA EE GOLOWKASME]AETSQ IZ Q^EJKI i W Q^EJKU i + 1 ILI NAOBOROT (TO ESTX PROHODITNAD \TOJ TO^KOJ).1),,-.
2).,,)(.41tEOREMA. pUSTX MA[INA tX@RINGA M RASPOZNAET QZYK L AI PUSTX SU]ESTWUET KONSTANTA c > 0 TAKAQ ^TO PRI RABOTE M NAL@BOM WHODNOM SLOWE a 2 A DLINA SLEDA W L@BOJ TO^KE NE PREWOSHODIT c tOGDA L REGULQRNYJ QZYK LEDOWATELXNO SU]ESTWUETAWTOMAT RASPOZNA@]IJ L S c = 1dOKAZATELXSTWO pUSTX a 2 A. pOSTROIM MNOVESTWO Da WSEHSLEDOW, KOTORYE MOGUT POLU^ITXSQ PRI RABOTE M NA SLOWAH WIDAax 2 A W TO^KE i, RAZDELQ@]EJ a I x.
pUSTX SLED qi1 qi2 qi3 : : : qis 2 Da.rASSMOTRIM RABOTU MA[INY M SLEWA OT RAZDELQ@]EJ TO^KI. oNA ODNOZNA^NO OPREDELQETSQ SLOWOM a I TEMI SOSTOQNIQMI qi2 ; qi4 ; : : : ; W KOTORYHNAHODITSQ MA[INA, KOGDA GOLOWKA WOZWRA]AETSQ NA LEWU@ ZONU ^EREZTO^KU i. pO USLOWI@ s 6 c. eSLI s | ^ETNO, TO MA[INA OSTANAWLIWAETSQSLEWA OT TO^KI i. w \TOM SLU^AE K POSLEDOWATELXNOSTI qi1 qi2 qi3 PRIPI[EM+, ESLI M OSTANAWLIWAETSQ W SOSTOQNII "PRINQTX", I PRIPI[EM ;,ESLI M OSTANAWLIWAETSQ W SOSTOQNII "OTWERGNUTX". tAK KAK s 6 c,TO WOZMOVNYH SLEDOW KONE^NOE ^ISLO I RAZNYH WOZMOVNYH MNOVESTWDa TAKVE KONE^NOE ^ISLO.
tOGDA UTWERVDENIE TEOREMY WYTEKAET IZSLEDU@]EJ LEMMY.lEMMA. eSLI Da = Db TO OSTATO^NYE QZYKI La = Lb SOWPADA@TdOKAZATELXSTWO pUSTX x - L@BOE SLOWO IZ A. rASSMOTRIM RABOTU M NA SLOWAH ax I bx. pUSTX qi1 qi2 qi3 : : : qis I qj1 qj2 : : : qjm | SLEDYW TO^KAH, RAZDELQ@]IH a I x, b I x. zAMETIM, ^TO RABOTA SPRAWA OTRAZDELQ@]IH TO^EK ODNOZNA^NO OPREDELQETSQ SLOWOM x I SOSTOQNIQMIqi1 qi3 qi5 : : : I qj1 qj3 qj5 : : : , W KOTORYH GOLOWKA PEREHODIT ^EREZ RAZDELQ@]IE TO^KI WPRAWO. pRI \TOM qi1 I qj1 ODNOZNA^NO OPREDELQ@TSQ PO a Ib.
tAK KAK Da = Db, TO qi1 = qj1 I RABOTA SPRAWA POSLE PERWOGO PEREHODA ^EREZ RAZDELQ@]IE TO^KI PROISHODIT ODINAKOWO. tOGDA qi2 = qj2 .oPQTX, TAK KAK Da = Db, TO qi3 = qj3 I OPQTX RABOTA SPRAWA PROISHODITODINAKOWO. pOSLEDOWATELXNO POLU^AEM, ^TO s = m I qir = qjr DLQ WSEHr = 1; 2; : : : ; s. eSLI s NE^ETNO, TO POSLE PEREHODA WPRAWO W SOSTOQNIIqis W OBOIH SLU^AQH RABOTA SPRAWA BUDET ODINAKOWOJ I, SLEDOWATELXNO,M OSTANOWITSQ W ODNOM I TOM VE SOSTOQNII. eSLI s ^ETNO, TO MA[INAW OBOIH SLU^AQH OSTANOWITSQ SLEWA OT RAZDELQ@]EJ TO^KI, PRI^EM WODNOM I TOM VE SOSTOQNII, POSKOLXKU Da = Db I SLED qi1 qi2 : : : qis W OBOIHMNOVESTWAH DOPOLNEN ODNIM I TEM VE ZNAKOM + ILI ;.
tAKIM OBRAZOM,M PRINIMAET SLOWO ax TOGDA I TOLXKO TOGDA, KOGDA ONA PRINIMAETSLOWO bx, TO ESTX LIBO OBA SLOWA WHODQT W L, LIBO OBA NE WHODQT W L.pO\TOMU La = Lb. |TIM DOKAZANA LEMMA, A WMESTE S NEJ I TEOREMA.,-.|. (C,,)..,-..42dOKAVEM TEPERX NESKOLXKO LEMM, KOTORYE ISPOLXZUEM W SLEDU@]EJ TEOREME.lEMMA. pUSTX A = fa1; a2; : : : ; arg ALFAWIT b1; b2; : : : ; bnRAZNYE SLOWA W \TOM ALFAWITE li DLINA SLOWA bi I lmax = maxi litOGDA lmax > c log2 n GDE c > 0 NEKOTORAQ KONSTANTA ZAWISQ]AQTOLXKO OT rdOKAZATELXSTWO wSE n SLOW IME@T DLINU, NE PREWOSHODQ]U@lmax.
nO WSEGO TAKIH SLOW MENX[E, ^EM rlmax +1 (SM. LEMMU). pO\TOMUn 6 rlmax +1, lmax > logr n ; 1 > c1 logr n = logc12 r log2 n. lEMMA DOKAZANA.lEMMAP. pRIUSLOWIQH LEMMY SU]ESTWUET KONSTANTA c > 0nTAKAQ ^TO i=1 li > cn log2 ndOKAZATELXSTWO ~ISLO WSEH pSLOWDLINYMENX[EJ, ^EM b 21 logr ncb 12 logr nc 6 r 12 logr n = n.
pO\TOMU SREDI SLOW bi NE MENEE,NE PREWOSHODITr^EM n ; pn SLOW, IME@T DLINU NE MENX[E ^EM b 12 logr nc. pO\TOMUnXpli > (n ; n)b 12 logr nc > cn log2 n|,,,||.|,..,..i=1DLQ NEKOTOROJ KONSTANTY c.lEMMA. pUSTX POSLEDOWATELXNOSTX n1; n2; : : : ; nk; : : : NE OGRANI^ENA SWERHU tOGDA IZ NEE MOVNO WYDELITX PODPOSLEDOWATELXNOSTXni1 ; ni2 ; : : : TAKU@ ^TO DLQ L@BOGO s I WSEH 1 6 j < is WYPOLNQETSQ-.,nj < nisdOKAZATELXSTWO pERWYM \LEMENTOM PODPOSLEDOWATELXNOSTIWOZXMEM n1.
pUSTX UVE WYBRANY ni1 ; ni2 ; : : : ; nir . tOGDA, PROSMATRIWAQ\LEMENTY PO PORQDKU POSLE nir , W KA^ESTWE O^EREDNOGO \LEMENTA WYBIRAEM PERWYJ \LEMENT nir+1 , BOLX[IJ, ^EM nir . eSLI WSE \LEMENTY njISHODNOJ POSLEDOWATELXNOSTI S j = 1; 2; : : : ; i2 ; 1 MENX[E, ^EM nir , TO,POSKOLXKU nir+1 > nir , A WSE \LEMENTY MEVDU nir I nir +1 NE PREWOSHODQTnir , TO WSE \LEMENTY nj S j = 1; 2; : : : ; ir+1 ; 1 MENX[E, ^EM nir +1.
tAKIMOBRAZOM PO INDUKCII PROWERQETSQ TREBUEMOE SWOJSTWO. tO, ^TO nir +1 SU]ESTWUET, SLEDUET IZ NEOGRANI^ENNOSTI ISHODNOJ POSLEDOWATELXNOSTI.oBOZNA^IM ^EREZ M (ab) SLED PRI RABOTE MA[INY tX@RINGA MNA SLOWE ab W TO^KE, RAZDELQ@]EJ a I b.lEMMA. pUSTX a; b; c NEKOTORYE SLOWA I PUSTX M (ajbc) =M (abjc) tOGDA PRI RABOTE M NA SLOWE ac SLEWA I SPRAWA OT TO^KIRAZDELQ@]EJ a I c MA[INA RABOTAET TAK VE KAK NA SOOTWETSTWU@]IH ^ASTQH PRI RABOTE NA abcdOKAZATELXSTWO rASSMOTRIM RABOTU MA[INY M NA SLOWE abcTOLXKO NA 2 ^ASTQH LENTY: SLEWA I SPRAWA OT b. pOSKOLXKU M (ajbc) =..|.,,,..43-M (abjc), TO PRI WYBRASYWANII ^ASTI LENTY, NA KOTOROJ ZAPISANO b, ISKLEIWANII OSTAW[IHSQ ^ASTEJ KORREKTNO "SKLEIWA@TSQ" I PROCESSYRABOTY M NA \TIH ^ASTQH.tEOREMA. pUSTX MA[INA tX@RINGA M RASPOZNAET QZYK L ApUSTX dM (n) MAKSIMALXNAQ DLINA SLEDOW W TO^KAH 1; 2; : : : ; n PRIRABOTE MA[INY M NA WSEH SLOWAH a A DLINY n A TM (n)MAKSIMALXNOE WREMQ WY^ISLENIQ ^ISLO [AGOW MA[INY M NA SLOWAHDLINY n IZ A tOGDA ESLI WYPOLNQETSQ HOTQ BY ODNO IZ DWUH USLOWIJA dM (n) = o(log n) B TM (n) = o(n log n) TO L REGULQRNYJ QZYKdOKAZATELXSTWO TEOREMY (OT PROTIWNOGO).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
