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



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


Работу автомата рассмотрим для входной цепочки abba. Если использовать последовательность команд (1),(4),(6.1),(5), то получим последовательность конфигураций:
 

      (s0,abba,h0)  |-- (s0,bba,h0a),    (1)
                          |-- (s0,ba,h0ab),       (4)
                          |-- (s0,a,h0abb),     (6.1)
                          |-- (s0,$,h0abba).    (5),

    которая показывает, что дальнейшая работа невозможна, т.к. входная цепочка прочитана и переход (s0,$,h0abba) не определен. Если же использовать последовательность команд (1),(4),(6.2),(3),(9), то получим заключительную конфигурацию:
     

        (s0,abba,h0) |-- (s0,bba,h0a),       (1)
                            |-- (s0,ba,h0ab),       (4)
                            |-- (s1,a,h0a),           (6.2)
                            |-- (s1,$,h0),              (3)
                            |--  (s2,$,$) .             (9).

      Т.о. можно сделать вывод о том, что цепочка abba допускается автоматом М2.
      В общем случае справедливо следующее утверждение.

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

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


       




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