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

   x   3.   nORMALXNYE ALGORITMY mARKOWA
       mARKOWSKIE PODSTANOWKI sHEMA NORMALXNOGO ALGORITMA nORMALXNYE ALGORITMY mARKO
                             .                                   .                          -

       WA nORMALXNO WY^ISLIMYE FUNKCII pRINCIP NORMALIZACII mARKOWA |KWIWALENTNOSTX
        .                                 .                                .

       OPREDELENIQ ALGORITMA W FORME NORMALXNYH ALGORITMOW mARKOWA OPREDELENIQM W FORME
       REKURSIWNYH FUNKCIJ I MAINY tX@RINGA      .




   3.1. mARKOWSKIE PODSTANOWKI. pUSTX X | NEKOTORYJ ALFAWIT, F0(X) | MNOVESTWO
WSEH SLOW W ALFAWITE X, WKL@^AQ I PUSTOE SLOWO, KOTOROE BUDEM OBOZNA^ATX ^EREZ I.
   pUSTX A
 B 2 F0(X). bUDEM GOWORITX, ^TO SLOWO B QWLQETSQ PODSLOWOM SLOWA A, ESLI DLQ
NEKOTORYH SLOW B1 
 B2 2 F0 (X) WYPOLNQETSQ RAWENSTWO:
                                        A = B1 BB2 .
   tROJKA hB1 
 B
 B2i NAZYWAETSQ WHOVDENIEM SLOWA B W SLOWO A.
pRIMER 1. pUSTX X | RUSSKIJ ALFAWIT (KIRILLICA), A = ABRAKADABRA, B = BRA. wIDIM, ^TO
B IMEET DWA WHOVDENIQ W A:
   PERWOE | h A, BRA, KADABRA i
   WTOROE | h ABRAKADA, BRA, Ii.
   pUSTX X | PROIZWOLXNYJ FIKSIROWANNYJ ALFAWIT. dLQ TROJKI SLOW A, B, C IZ F0(X) OBO-
ZNA^IM ^EREZ
                                                SubCB (A)
SLOWO, POLU^ENNOE IZ A ZAMENOJ PERWOGO WHOVDENIQ SLOWA B W A NA SLOWO C, ESLI B QWLQETSQ
PODSLOWOM  SLOWA A. eSLI VE B NE QWLQETSQ PODSLOWOM SLOWA A, TO BUDEM S^ITATX, ^TO WYRAVENIE
SubCB (A) NE OPREDELENO.
pRIMER 2. SubIBRA(ABRAKADABRA) = AKADABRA,
   SubLBRA (ABRAKADABRA) = ALKADABRA,
   SubBRA
       BRA (ABRAKADABRA) = ABRAKADABRA,
      BRA
   SubBRE (ABRAKADABRA) NE OPREDELENO,
   SubV
      I(ABRAKADABRA) = VABRAKADABRA.
    oTMETIM, ^TO SubCB (A) ESTX ^ASTI^NAQ TREHMESTNAQ OPERACIQ NA F0(X). eSLI VE SLOWA B I C
ZAFIKSIROWANY, TO SubCB (A), A 2 F0(X) ESTX ^ASTI^NAQ ODNOMESTNAQ OPERACIQ NA F0 (X). bUDEM
EE OBOZNA^ATX FORMULOJ WIDA:
                                          B!C
I NAZYWATX MARKOWSKOJ PODSTANOWKOJ NA F0 (X), A SAMO WYRAVENIE B ! C | FORMULOJ DANNOJ
MARKOWSKOJ PODSTANOWKI.
   pRI \TOM B BUDEM NAZYWATX LEWOJ ^ASTX@ (POSYLKOJ ), A C | PRAWOJ ^ASTX@ (ZAKL@^ENIEM )
DANNOJ MARKOWSKOJ PODSTANOWKI. eSLI SubCB (A) NE OPREDELENO, TO BUDEM GOWORITX, ^TO FORMULA
B ! C NE PRIMENIMA K SLOWU A.
oPREDELENIE 1. sHEMOJ NORMALXNOGO ALGORITMA W ALFAWITE X NAZYWAETSQ POSLEDOWATELX                 -
NOSTX WIDA:
                                              B1 !
                                       8
                                       >
                                       >                C11 

                                              B2 !
                                       >
                                       <                C22 
                                  (1)
                                       >
                                       >      ::: :::   ::::::
                                              Bs !
                                       >
                                       :
                                                        Cs s

GDE Bi ! Ci, i = 1
 : : :
 s, | NEKOTORYE FORMULY MARKOWSKIH PODSTANOWOK W F0(X), A 1
 : : :
 s 2
2 fI
 g. pRI \TOM PODSTANOWKU Bi ! Cii BUDEM NAZYWATX ZAKL@^ITELXNOJ, ESLI i = .
                                                  137