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


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

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

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


  •  




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