Формальные языки



Язык, допускаемый магазинным автоматом


 

    Определение. Цепочка  a

    называется допустимой для автомата М, если существует последовательность конфигураций, в которой первая конфигурация является начальной c цепочкой a , а последняя - заключительной. (sо, a, hо) |--* (s1, $ , $) , где s1 О

    F .

 

    Определение.Множество цепочек, допускаемых автоматом М, называется языком, допускаемым или определяемым автоматом М, и обозначается L(М).

 

      L(М)= {a ¦ ( sо, a, hо ) ¦--* ( s', $, $)   &  s' О F }

    Чтобы лучше представить себе работу магазинного автомата, рассмотрим два примера. Пусть задан магазинный автомат М1 в следующем виде:
     

        М1:    P = {a , b};  S = {s0 , s1 , s2};  H = {h0 , a};  F = {s0};

          f (s0 , a , h0) = (s1 , h0a),


          f (s1 , a , a) = (s1 , aa),


          f (s1 , b , a) = (s2 , $),


          f (s2 , b , a) = (s2 , $),


          f (s2 , e

          , h0) = (s0 , $).

         

      Этот автомат является детерминированным, поскольку каждому набору аргументов соответствует единственное значение функции. Работу автомата при распознавании входной цепочки aabb можно представить в виде последовательности конфигураций:
       
                (s0,aabb,h0) |--  (s1,abb,h0a) |-- (s1,bb,h0aa) |-- (s2,b,h0a) |-- (s2,$,h0) |-- (s0,$,$) .

      Нетрудно проверить, что при задании входной цепочки aabbb автомат не сможет закончить работу. Следовательно эта цепочка не принадлежит языку, допускаемому автоматом  M1.
      Магазинный автомат М2, заданный следующим описанием:
       

          М2:     P = {a , b}; S = {s0, s1 , s2}; H = {h0, a , b}; F = {s2};

            (1)f (s0 , a , h0) = (s0, h0a),


            (2)f (s0 , b , h0) = (s0, h0b),


            (3) f (s0 , a , a) = {(s0,aa) , (s1 , $)},


            (4) f (s0 , b , a) = (s0,ab),


            (5) f (s0 , a , b) = (s0 , ba),


            (6) f (s0 , b , b) = {(s0 , bb) , (s1 , $)},


            (7) f (s1 , a , a) = (s1, $),


            (8) f (s1 , b , b) = (s1, $),


            (9) f (s2 , e

            , h0) = (s2 , $),

          является недетерминированным автоматом, поскольку одному и тому же набору аргументов, например (sо , a, a), соответствуют два значения функции.


          Содержание  Назад  Вперед