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



Пример работы расширенного магазинный автомат


В качестве иллюстрации работы расширенного автомата рассмотрим автомат, допускающий язык L={wwR | w О {a, b}*}.

M7.1:    P = {a, b}, S = {s0, s1},  H = {a, b, <I>, h0}, F = {s1} ,


 

    d(s0, a, h0) = (s0, h0a),                  d(s0, a, <I>) = (s0, <I>a),


    d(s0, b, h0) = (s0, h0b),                 d(s0, b, <I>) = (s0, <I>b),


    d(s0, a, a) = (s0, aa),                     d*(s0, a, a<I>a) = (s0, <I>),


    d(s0, b, a )= (s0, ba),                    d*(s0, b, a<I>a) = (s0, <I>),


    d(s0, a, b) = (s0, ab),                    d*(s0, a, b<I>b) = (s0, <I>),


    d(s0, b, b) = (s0, bb),                   d*(s0, b, b<I>b) = (s0, <I>),


    d*(s0, a, aa) = (s0, <I>),              d*(s0, $, a<I>a) = (s0, <I>),


    d*(s0, b, aa) = (s0, <I>),              d*(s0, $, b<I>b) = (s0, <I>),


    d*(s0, a, bb) = (s0, <I>),              d*(s0, $, h0<I>) = (s1, $).


    d*(s0, b, bb) = (s0, <I>),

Это недетерминированный автомат. Если на входе задана цепочка abba, то его работу можно представить в виде следующего ряда конфигураций:
 


     

     Вход

     Магазин

     Состояние

    1.

     abba|-

     h0

     s0

    2.

     bba|-

     h0a

     s0

    3.

     ba|-

     h0ab

     s0

    4.

     a|-

     h0abb

     s0

    5.

     a|-

     h0a<I>

     s0

    6.

     |-

     h0a<I>a

     s0

    7.

     |-

     h0<I>

     s1