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

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

L(М)= {a ¦ ( s_о, a, h_о ) ¦--* ( s', $, $)   &  s' О F }

М₁:    P = {a , b};  S = {s₀ , s₁ , s₂};  H = {h₀ , a};  F = {s₀};
f (s₀ , a , h₀) = (s1 , h₀a),
f (s₁ , a , a) = (s₁ , aa),
f (s₁ , b , a) = (s₂ , $),
f (s₂ , b , a) = (s₂ , $),
f (s₂ , e , h₀) = (s₀ , $).
 

Нетрудно проверить, что при задании входной цепочки aabbb автомат не сможет закончить работу. Следовательно эта цепочка не принадлежит языку, допускаемому автоматом  M₁.
Магазинный автомат М₂, заданный следующим описанием:
 

М₂:     P = {a , b}; S = {s₀, s₁ , s₂}; H = {h₀, a , b}; F = {s₂};
(1)f (s₀ , a , h₀) = (s₀, h₀a),
(2)f (s₀ , b , h₀) = (s₀, h₀b),
(3) f (s₀ , a , a) = {(s₀,aa) , (s₁ , $)},
(4) f (s₀ , b , a) = (s₀,ab),
(5) f (s₀ , a , b) = (s0 , ba),
(6) f (s₀ , b , b) = {(s₀ , bb) , (s₁ , $)},
(7) f (s₁ , a , a) = (s₁, $),
(8) f (s₁ , b , b) = (s₁, $),
(9) f (s₂ , e , h₀) = (s₂ , $),

(s₀,abba,h₀)  |-- (s₀,bba,h₀a),    (1)
                    |-- (s₀,ba,h₀ab),       (4)
                    |-- (s₀,a,h₀abb),     (6.1)
                    |-- (s₀,$,h₀abba).    (5),

(s₀,abba,h₀) |-- (s₀,bba,h₀a),       (1)
                    |-- (s₀,ba,h₀ab),       (4)
                    |-- (s1,a,h₀a),           (6.2)
                    |-- (s₁,$,h₀),              (3)
                    |--  (s2,$,$) .             (9).