Дискретная математика. Кулабухов С.Ю. - 138 стр.

gLAWA    VII.   oSNOWY TEORII ALGORITMOW

       3.2. oPREDELENIE NORMALXNOGO ALGORITMA mARKOWA. pUSTX DAN NEKOTORYJ ALFAWIT
X I NEKOTORAQ SHEMA (1) NORMALXNOGO ALGORITMA W \TOM ALFAWITE.
   nORMALXNYM ALGORITMOM mARKOWA (N. A. m.) W ALFAWITE X, OPREDELENNYM SHEMOJ (1), NA-
ZYWAETSQ OPISYWAEMYJ PROCESS POSTROENIQ POSLEDOWATELXNOSTI SLOW Ai , i = 0
 1
 : : :, ISHODQ IZ
DANNOGO SLOWA A.
  1. eSLI i = 0, TO POLAGAEM A0 = A I S^ITAEM, ^TO PROCESS POSTROENIQ POSLEDOWATELXNOSTI
     SLOW E]E NE ZAWEREN.
  2. pUSTX i  0, SLOWA A0 
 : : :
 Ai POSTROENY I PROCESS POSTROENIQ SLOW E]E NE ZAWERILSQ.
     tOGDA:
      (a) ESLI KAVDAQ IZ PODSTANOWOK SHEMY (1) NEPRIMENIMA K SLOWU Ai , TO POLAGAEM Ai+1 = Ai ,
          PROCESS POSTROENIQ SLOW S^ITAEM ZAWERENNYM I SLOWO Ai+1 S^ITAEM REZULXTATOM
          PRIMENENIQ N. A. m. K SLOWU A
      (b) ESLI SREDI PODSTANOWOK SHEMY (1) ESTX PRIMENIMYE K SLOWU Ai , TO Ai+1 ESTX SLOWO,
          POLU^ENNOE IZ Ai PRIMENENIEM PERWOJ PRIMENIMOJ K NEMU PODSTANOWKI IZ SHEMY (1)
          PRI \TOM, ESLI \TA PODSTANOWKA BYLA ZAKL@^ITELXNOJ, TO PROCESS POSTROENIQ SLOW
          S^ITAETSQ ZAWERENNYM I Ai+1 S^ITAETSQ REZULXTATOM PRIMENENIQ N. A. m. K SLOWU A
          ESLI VE PRIMENENNAQ PODSTANOWKA NE QWLQLASX ZAKL@^ITELXNOJ, TO PROCESS POSTROENIQ
          POSLEDOWATELXNOSTI SLOW S^ITAETSQ NEZAWERENNYM.
   tAKIM OBRAZOM, ESLI N. A. m., PRIMENENNYJ K SLOWU A, ZAWERAETSQ NA SLOWE B, TO GOWORQT,
^TO N. A. m. PERERABATYWAET SLOWO A W SLOWO B. eSLI VE N. A. m., PRIMENENNYJ K SLOWU A,
NIKOGDA NE ZAWERAETSQ, TO GOWORQT, ^TO DANNYJ N. A. m. NEPRIMENIM K SLOWU A. w DALXNEJEM
BUDEM PISATX Ai ) Ai+1 .
       3.3. pRIMERY NORMALXNYH ALGORITMOW mARKOWA. 1. pUSTX X = fx1
 x2
 : : :
 xng. rAS-
SMOTRIM SHEMY N. A. m.:
                                                   !
                                             (
                                                 x1         I                                  (2)
                                                 I !        I
                                                I !         I
                                             (
                                                                                              (20)
                                               x1 !         I
                                               x1 !
                                             (
                                                            x2                                 (3)
                                                 I !        I
                                               x1 !         x1 
                                             (
                                                                                               (4)
                                                I !         I
                                               x1 !
                                             (
                                                            x1x1                               (5)
                                                I ! I
   oTMETIM, ^TO N. A. m. (2) WSQKOE SLOWO A, SODERVA]EE WHOVDENIQ BUKWY x1 , PERERABATYWAET W
SLOWO A0 , POLU^ENNOE IZ A WY^ERKIWANIEM WSEH WHOVDENIJ BUKWY x1. eSLI VE SLOWO B NE SODERVIT
WHOVDENIJ BUKWY x1, TO N. A. m. (2) PERERABATYWAET EGO W SEBQ. n. A. m. (20) PERERABATYWAET WSQKOE
SLOWO W SEBQ.
   n. A. m. (3) PERERABATYWAET SLOWA, NE SODERVA]IE W SWOEJ ZAPISI BUKWY x1, W SEBQ, A SO-
DERVA]IE | W SLOWA, POLU^A@]IESQ IZ ISHODNYH ZAMENOJ WSEH WHOVDENIJ BUKWY x1 NA BUKWU
x2 .
   n. A. m. (4) WSQKOE SLOWO PERERABATYWAET W SEBQ.
   n. A. M. (5) WSQKOE SLOWO, NE SODERVA]EE WHOVDENIJ BUKWY x1, PERERABATYWAET W SEBQ. k
OSTALXNYM SLOWAM ON NE PRIMENIM. dEJSTWITELXNO,
                    x2x1x3 x1 ) x2x1x1 x3x1 ) x2x1 x1x1x3 x1 ) x2x1x1 x1x1x3 x1 ) : : :

                                                      138