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


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


В качестве иллюстрации работы расширенного автомата рассмотрим автомат, допускающий язык 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

 

       

 

Пред.Страница 

След.Страница   Раздел   Содержание 




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