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

                                                                           x 2. mAINY tX@RINGA

   rABOTA MAINY tX@RINGA PREDSTAWLQET SOBOJ POAGOWYJ PEREHOD OT ODNOGO SOSTOQNIQ K
DRUGOMU. oDIN AG ILI TAKT | \TO PEREHOD OT MAINNOGO SLOWA M K MT0 , SM. P. VII.2.2. |TOT
PEREHOD OSU]ESTWLQETSQ PO NIVESLEDU@]IM PRAWILAM 1{2.
  1. pRI i = 0, MT0 = M. |TO OZNA^AET, ^TO ESLI MAINA POPALA W SOSTOQNIE q0, TO ONA S^ITAETSQ
     OSTANOWIWEJSQ. eSLI VE W MAINE NE PROISHODIT IZMENENIJ W SOSTOQNII, OTLI^NOM OT q0,
     TO BUDEM GOWORITX, ^TO MAINA RABOTAET WE^NO.
  2. pUSTX i > 0.
      (a) eSLI T(i
 j) = (qi aj ! qk al ). wNUTRENNEE SOSTOQNIE MAINY qi ZAMENQETSQ NA qk (WOZ-
          MOVNO, qi = qk ). sODERVIMOE OBOZREWAEMOJ Q^EJKI aj ZAMENQETSQ NA al (WOZMOVNO,
           aj = al ).
      (b) eSLI T (i
 j) = (qi aj ! qk R), TO WNUTRENNEE SOSTOQNIE qi ZAMENQETSQ NA qk I UPRAWLQ@-
           ]AQ GOLOWKA SDWIGAETSQ WPRAWO NA ODNU Q^EJKU, PRI \TOM, WOZMOVNO, PRISTRAIWAETSQ
           SPRAWA ODNA Q^EJKA W PUSTOM SOSTOQNII.
       (c) eSLI T (i
 j) = (qi aj ! qk L). oSU]ESTWLQETSQ WSE TO, ^TO W PREDYDU]EM PUNKTE S
           ZAMENOJ \PRAWO" NA \LEWO".
   tAKIM OBRAZOM, S MATEMATI^ESKOJ TO^KI ZRENIQ MAINA tX@RINGA | \TO OPREDELENNYJ AL-
GORITM DLQ PERERABOTKI MAINNYH SLOW.
pRIMER 1. pUSTX T = hA
 Q
 P i, GDE: A = f0
 1g, Q = fq0
 q1
 q2g,
    P : q10 ! q2R, q11 ! q1R,
          q20 ! q01, q21 ! q2R.
   iMEEM:
   1) q1110 j= 1q110 j= 11q10 j= 110q20 j= 110q01.
   2) q10110 j= 0q2110 j= 01q210 j= 011q20 j= 011q01.
   |TO OZNA^AET, ^TO: q1110 ) 110q01 I q1 0110 ! 011q01.
   lEGKO PONQTX, ^TO:
                                       q101110 ) 0111q01
                                       q1011110 ) 01111q01
                                       : : :: : :: : :: : :: : :: : :: : :
                                       q10 1| :{z: :1} 0 ) 0 |1 :{z: :1} q0 1:
                                          n           n
pRIMER 2. pUSTX T = hA
 Q
 P i, GDE A = f0
 1g, Q = fq0
 q1
 q2
 q3g,
    P: q10 ! q2R, q21 ! q2R,
          q11 ! q1R, q30 ! q3L,
          q20 ! q3L, q31 ! q00.
   iMEEM:
   1) q100 j= 0q20 j= q300 j= q3000 j= q30000 j= : : : tAKIM OBRAZOM, W \TOM SLU^AE MAINA RABOTAET
WE^NO.
   2) q1010 j= 0q210 j= 01q20 j= 0q310 j= 0q000, TO ESTX q1010 ) 0q000.
   lEGKO PONQTX, ^TO:
                                      q1010 ) 0q000
                                      q10110 ) 01q000
                                      q101110 ) 011q000
                                      : : :: : :: : :: : : : : :: : :
                                      q10 1| :{z: :1} 10 ) 0 1| :{z: :1} q000
                                         n            n
    sLEDUET PONIMATX, ^TO MAINA tX@RINGA QWLQETSQ ABSTRAKTNYM MATEMATI^ESKIM OB_EKTOM
I PREDSTAWLQET SOBOJ PROSTO OPREDELENNYJ ALGORITM DLQ PERERABOTKI SLOW W NEKOTOROM ALFAWI-
TE.
                                               133