..ᠭ쥢, ..祭   "᭮ 樨"  ᥭ,1991

   ਠ  樨 2.  ᪮.  모.

   䨪 ࠬ⨪  ᫮  ᮮ⢥  ண
ࠬ-ᯮ⥫ 뢠 娥 ᪮.   뤥
 4  ࠬ⨪ ( 浪 ⠭ ᫮):
    ) ॣ ( ⮬). ࠢ  :
           A : xB  A : x,  x - 楯窠 ନ  e
           ਬ - ࠦ.
    ) ⥪⭮-᢮ ( ). ࠢ  :
           A : y,  y - 楯窠  ନ  ନ
           ਬ - "᪮  "    ।饩  樨,
            䬥᪨ 
    ) ⥪⭮-ᨬ  (㪮稢騥).  ࠢ  
        :
           z : y,  z  y - 楯窨  ନ   ନ
           , z ᮤন ନ, |z| <= |y|
                    n n n
           ਬ: a b c
    )  ࠭祭

    몠 । ᮬ  ᠬ  ⮩  (  ᫥
娨 ᪮)  뢠  ࠬ⨪. 騥 
    ᮢ  몮  祢,  ᫨    ᬠਢ
-ࠬ⨪, ᮤঠ騥 ⠪ 뢠 e-ࠢ - ࠢ  
⮩ ࠢ . (ࠦ: ,    -
  ᠭ ࠬ⨪  e-ࠢ).

  <  <  < ४ᨢ ⢠ <  = ४.᫨ -

    몠, । ॣ୮ ࠬ⨪, ᥣ 
  ⥪⭮-᢮ ࠬ⨪ (   ࠬ⨪
 ࠭祭!).   ,   ண:  
  모,    ࠬ⨪ 
 ⮣ .

                        ⮬

   ᬮਬ 㣮 ᯮᮡ  ॣ  몮.  (
ନ஢)  ⮬ :
 - 䠢⮬ 室 ᨬ E;
 - ⢮ ﭨ S;
 - ୠ ⭮襭 室  ⢥ { S, E U e, S };
 - 砫 ﭨ - 뤥 ﭨ  S, 
 - 묨 ﭨﬨ -  ⢮ S.
ਭ ࠦ ⮬   ਥ஢ ,  㧫
ண ᮮ⢥ ﭨ ( ﭨ   㤥
   ࠬ),  ॡ, 祭 ᨬ 室
 䠢  , ࠦ ⭮襭 室.
   窠 ᪠ ⮬⮬ ᫨  ⮫쪮 ᫨  
  砫쭮      ﭨ,  ⠪  ,
⠢ ⪨ ॡ  ⮣ ,  稬 室  
 (㪢 e, ⢥,  ⠥). ਬ, ⮬

            Ŀ  0  Ŀ  1  ¿
               S   >Ĵ   B   >Ĵ  C  
                      
                              <0

᪠ 楯窨 (01)+.         ॣ୮
ࠬ⨪:

        S : 0 B     B : 1 C     C : 0 B     C : e

   ᫮  (ࠦ),        ⮬
 ந ॣ ࠬ⨪, 뢠   ᠬ
,  .

   ନ஢  ⮬ -    砩  
ନ஢,  ஬:
 -  e-室,
 - ⭮襭 室  筮 㭪樥 

         f:( S x E U e ) -> S,

।,  ,      SxEUe.   ନ
  砥,    ﭨ  室    
 ॡ   ⪮.

    ନ஢ ⮬ 祭  ஢  
 楯窨  E* . , ᫨ 㦭,   
"㯨" ﭨ,  ᤥ 㭪 室  ।
     S x E.

    Ŀ
        0  1    s := 砫쭮 ﭨ
    Ĵ   横   ᨬ 楯窨 c 믮
     S  B  F    . s := f( s, c )
     B  F  C     横
     C  B  F    ⢥ := s - 筮 ﭨ
     F  F  F 
    

      ନ஢  筮  ⮬
 來  饯ਭ: KA -  ன⢮,  ஥  
室  筮 ⢥ ﭨ  室   
ﭨ  㣮e  ⢨ 譨 ᮡ⨩  䠢 E.
      ࠧ ஢ ନ஢
 ⮬ (   䥪⨢  ।  ਭ
楯窨 )? ,  ,   ⮬ 砥,  
  祬  室, ᮧ 室  ᫮  
஢ ,  ॢ     ⮩ 
樨 ﭨ. 窠 ⠥ 饭, ᫨   
 ஢   筮 ﭨ.

               <Ŀ0
           Ŀ  0  Ŀ  1  ¿
              S   >Ĵ   B   >Ĵ  C  
                     
                             <0

 楯窨 ᪠  ⮬? - ࠦ.
   ⨬,  ᫨ ᪮쪮 ஢ ନ஢
    ﭨ,   쭥襬   ᬠ
ਢ ⮫쪮   .   ࠧ,  ᨬ쭮  
⢮ ஢  ॢ室 ᫠ ﭨ.
   ஢, ᪠  ନ஢  ⮬
楯 ᨬ, ⠪ ᫮:

        S := e-몠( { 砫쭮 ﭨ } )
        横   ᨬ 楯窨 c 믮
        . S := e-몠( F( S, c ) )
         横
        ⢥ := ( S   ﭨ ) - 

:  S                - ⢮ ⢠ ﭨ KA;
        e-몠( S ) - ⢮ ﭨ, ⨦  S
                            0   e-室;
        F( S, c )        - ⢮ ﭨ, ⨦  S
                          室, 祭 ᨬ c.

   ࠦ  ணࠬ஢: ਤ㬠   
 ।⠢ ନ஢  ନ஢ 
 ⮬⮢  ணࠬ ஢ ᪠ ப  
ᨬ ASCII KA.   ( ᫥)   ६
- O( 楯窨)                   ନ஢ 
- O( 楯窨*᫮ ﭨ)  ନ஢ .


  ८ࠧ ନ஢   ନ஢

   ନ஢  ᥣ  ८ࠧ   
 (.. ᪠騩   ⢮ 楯祪) ନ
 . ᬮਬ  , ﭨﬨ ண  
⢠ ⢠ ﭨ 室  (᫨ 室 
  m ﭨ, ᪮쪮  㤥  ? - ࠦ).
室   ⮬ 㤥 ﭨ {砫}, 
 -  ﭨ, ᮤঠ騥 室 筮 ﭨ. 
室 A > B  ᨬ d       ⮬  ⮣  
⮫쪮 ⮣,   室 ⮬   ﭨ  b
 B,  a  A ⠪,   ᨬ d   
室 a > b,  㣨 室  d  A .  ⮬ 
 ନ஢   室.
    ⢨⥫쭮, ﭨ  ⮬ a+b  ᮮ⢥
ࠧ饭 ஢ 室 ନ஢   
ﭨ a  b,  室   ⮬ ᮮ⢥ 
  ஢ ନ஢ .
    ࠪ᪨ 楫 ਬ  : 
 ﭨ ࠧ稬묨, ᫨   ந室 室 
  ⮣  ﭨ    ⮬  室  ᨬ.
쬥  ⢮ ࠧ稬 ﭨ    ᯨ
᮪ ﭨ    -  "㬬", ६ 室:

       뫮:                            ⠫:
Ŀ1 Ŀ0 Ŀ                  Ŀ1 Ŀ0
 >>                   >+>>
                           
 1 Ŀ0 Ŀ                     Ŀ0  
 >>                     > 
                           
Ŀ1                          Ŀ1 Ŀ0    
>                        >>Ĵ
                                   

稬  ( ,  ନ஢) . 㤥
  ⢨,     ࠧ稬 
ﭨ.     殢  (祬? -  ࠦ
).  ⮬  稬 ନ஢ ⮬,  
 室 (祬? - ࠦ).
   ਬ  ⮤  ନ஢    ਬ  
⮩ 樨, 稬:
                                     <Ŀ 1
       Ŀ 0  Ŀ 1  ¿0  Ŀ
          S   >Ĵ   B   >Ĵ  C  >  S + B  
                  
                        < 0

                  筮 ⮬

    筮 ⮬   ந ⮬   
訬 ᫮ ﭨ,  室.  ⢥騩
 뢠  樥  筮  ⮬.  砫
ᨬ  ⮬  ﭨ, ⨦  砫쭮.
⥬ ࠧ쥬  ﭨ    ⭮  ᫥
騬 ᯮᮡ:    ⭥ᥬ   ﭨ,
  ன -  ⠫.     ﭨ  0-
묨.  ந  1-⭮ ࠧ,  
  ﭨ,    ᨬ 室  
0- ﭨ.  ᫥⥫쭮    n+1-
 ﭨ  n-,  㤥 㢥稢 
 ᮢ ⭮. ४⨬   ⮣, 
n+1-⭮ ﭨ ᮢ  n-.  
祭  ⭮  㤥 ﭨ   
஢ , ⭮ 室 (祬? -  ࠦ
).
   ᬮਬ, ਬ, ᫥騩 :

                Ŀ1   ¿ 0Ŀ
     Ŀ0>   B   >Ĵ  D  <Ĵ   F   
     砫      
                  <0 > 1   > 1
                                       
                <Ŀ0 1 <    0 <
       A   Ŀ Ŀ1  ¿ 1Ŀ
     1>   C   >Ĵ  E  <Ĵ   G   
                      

ﭨ F  G ⨦ (  ᭨, ਬ,  
᫨ ࠭⨢ 몠 ⭮襭 "  室").  
ந  n-⭮  ⠢ ﭨ:
       n        
       0      (ABC) (DE)
       1      (A) (BC) (DE)
       2      (A) (BC) (DE)
:

            Ŀ0,1  Ŀ1    ¿
              A  > B+C >D+E
                      
                           <0

   ࠦ:  ,             
⢥   筮    䨧    
   ⮬. ,  ᠭ   
 樨 砥  室  ⮬.
   ࠦ  ணࠬ஢: ਤ㬠   
 ணࠬ 楤 ஥ ନ஢ ,
 樨 .  ६  ࠭⢥  ᫮
।  ⬮  ନ ᫠ ﭨ  室
  室 ⮬⮢?


             모  ॣ ࠦ

   ᬮਬ ᯥ樠  権  몠 - ॣ
 樨, ⢮ 몮, 砥  १  ਬ
 筮 ᫠ ॣ 権    
, - ॣ ⢠, ᯮᮡ   ᠭ  -  ॣ
ࠦ  ନ஢  ⮬,  ᪠騥
楯窨   .

Ŀ
    ୮      ୮      ⮬        
     ⢮       ࠦ                             
Ĵ
   楯窠         e        Ŀ   e   ¿    
                                    S  >Ĵ E     
                                             
Ĵ
  ᨬ a  E      a        Ŀ      ¿    
                                    S  >Ĵ E     
                                             
Ĵ
                                Ŀ e Ŀ e ¿
  P U Q                 p|q        >Ĵs.Pe>Ĵ 
                                 S       E
                                    e Ŀ e  
                                   >Ĵs.Qe>Ĵ 
                                      ٳ
Ĵ
  PQ (⥭)     pq      ¿ 
                                 S .P es .Q 
                                 
Ĵ
  P* ()         p*               <Ŀe        
                                Ŀ e  e ¿
                                 S >Ĵs.Pe>ĴE
                                      ٳ
                                 e>  
Ĵ
   P ( ᪮)    (p)        ¿   
                                     S   .P  E    
                                      


    ॣ୮ ࠦ "*"  訩 ਮ, 祬 
⥭,  ⥭ - 訩 祬 "|". ਬ ॣ
ࠦ: (0|1)*, (0|1)(0|1)*.  ⢠  뢠?
    ॣ୮ ࠦ । ᯮᮡ ஥  
ନ஢ 筮 ⮬, ᪠饣  ᮮ⢥
饥 ࠦ ॣ୮ ⢮.  ।  
  ᠬ    (⮬  筮  ᮤন  
"譨"  e-室),    ஥  ⮬  
᫥騬 묨 ᢮⢠:
 -   ⮫쪮  筮 ﭨ,
 -  砫쭮 ﭨ  室   ॡ,
 -  筮 ﭨ  室   ॡ.
    ࠧ,  ,  ॣ ⢠ < ॣ
 모 = 모, ᪠ . ,   ᪠
 ⢮ - ॣ୮. ( ⢥ত 뢠  ⥮६
).
   ⥫⢮:  S1,...Sn - ﭨ ନ஢
 , S1 - 砫쭮 ﭨ. ᬮਬ       
室  砫  Si, 殬  Sj, ஬묨 㧫 
⢠ {S1...Sk} (1<=i<=n, 1<=j<=n, 0<=k<=n)  ⢠ 
祪  E - L(i,j,k), ᮮ⢥騥 ⨬ .   
樥  k,  ⢠ L - ॣ.
   L(i,j,0) - ⮨  ⮪ ॡ,   Si  Sj,  ᫥
              ⥫쭮, ॣ୮.
 0<=k<=n-1
   L(i,j,k+1) = L(i,j,k) U  L(i,k+1,k) L(k+1,k+1,k)* L(k+1,j,k)
   祭   ॣ 権    ॣ  
   , ᫥⥫쭮, ॣ୮.

⢮ 楯祪, ᪠ , ।⠢  ᮡ  ꥤ
 楯祪 L(1,j,n), ⠪,  Sj - 筮 ﭨ  ,
᫥⥫쭮, ॣ୮. ( ⥫⢠).

    ᬮ५ 4 ᯮᮡ ᠭ 몮:
 - ॣ (⮬, ࠢ) ࠬ⨪,
 - ନ஢ ,
 - ନ஢ ,
 - ॣ ࠦ,
 ,   뢠    몮  -  ॣ
모.   몮 "஥ 祭 " -    
 ᮢ  ⢥  䥪⨢ . ਬ
 ⠪ ᮢ (祭 ⢥⮢ - ࠦ):
 -   ꥤ, 祭,   ॣ
   몮 ॣ,
 -   ॣ  , ,
 - ᮢ   ॣ 몠,
 -    ॣ  ⢮ 㣮,
    ..

(砭.  㣨 ᮢ 娨 ᪮    
⥫쭮  㦥,  ਬ,  ஡   ⭮   
-몮 ⬨᪨ ࠧ訬.)

             ࠧ⠭  ॣ 몮

    뢠 "  ࠧ⠭"    ᮢ  몮  -
㤮 ᯮᮡ ⥫⢠ ⮣,      
   .
     ॣ୮ 몠:  ⠪ ᫮  m,  
 楯 x, |x| > m, ਭ ,  ࠧ 
 : x = uvw ⠪,  0<|v|<=m  楯窨 uv*w ⠪ 
ਭ . ⥫⢮: ந   ᯮ
 몠.   ⮬  m ﭨ.   ࠧ
 楯窨 x     ﭨ (ਬ,  )  
  (祬? - ࠦ). 쥬 楯 x   
 -  ﭨ ,    , ⠫쭮.    楯
 u,v,w (祬 v   ࠧ,  ࠭  ਭ
楯窨 ? - ࠦ).
                           n n
    ,   0 1   ॣ? -  ࠦ
.

                       ࠦ

   1.  ॣ ࠬ⨪    ॣ୮  ࠦ,
஦騥   ,   ࠬ⨪:
   S : AB ;   A : X|Y ;   X : x|xX ;   Y : y|yY ;   B : b|bB

   2. ந ॣ ࠬ⨪   ⮬, ᮮ
騥 ॣ୮ ࠦ:

        (101)*(010)*

   3. ன ନ஢   ⥬  ନ஢
 ⮬, ਭ騥 ॣ୮ ࠦ:

        (101)*(110)*

   4. ந ନ஢  ⮬   ᫥
 ॣ ࠦ.      祭  ⮬
ந   ⮬.     
䨧  ⮬⮢, ᫥⥫쭮,  ⭮
 室 ࠦ:
   (a|b)*   (a*|b*)*   ((e|a)b*)*

   5.  ॣ୮ ࠦ, 뢠饥 ᫥騩 
 - ᫮, 㪢 ண ᯮ  䠢⭮ 浪
 - ᫥⥫쭮 ,  ன   
 - ᫥⥫쭮 ,  ன   祬    
   砥 ᪮쪮 ࠧ
 - ப  㫥  ,  ன  ப 0 0 1
 - ப  㫥  ,   ன    ᫥⥫
    0 0 1

   6.  ॣ୮ ࠬ⨪  ਢ ॣ୮ 
ࠦ  䨪 ࠭. (  㪢    ,
 ᨬ   㪢).

   7.  ணࠬ ᯮ  ⢥  ⠭.
  ਭ ⠭ :

1.2  -0.4 +3.14 .2 1. -1.38 1+2 +0.5-23  ..

   8. ந  ନ஢  ⮬
 ᫥ ॣ ࠦ
   (a|b)*a(a|b)
   (a|b)*a(a|b)(a|b)
   (a|b)*a(a|b)(a|b)(a|b)
,   ନ஢  ⮬   
ࠦ (a|b)a(a|b)(a|b)...(a|b), ᮤঠ饣 n-1 (a|b)  
ᮤন   祬 2**n ﭨ.

   9.  ணࠬ,  ஢,      
䠩  砥 ࠧ  ॣ୮  ࠦ,  
஬ ᨬ * 砥  ( ⮬  ᫥    )
᫥⥫쭮 ᨬ ஬ ".",  ᨬ ?  -  
ᨬ ஬ "."

                -  ਠ  樨 2 -
