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


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


 

    Определение. Цепочка  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), соответствуют два значения функции.


- Начало -  - Назад -  - Вперед -