Язык, допускаемый магазинным автоматом
называется допустимой для автомата М, если существует последовательность конфигураций, в которой первая конфигурация является начальной c цепочкой a , а последняя - заключительной. (sо, a, hо) |--* (s1, $ , $) , где s1 О F . |
|
- L(М)= {a ¦ ( sо, a, hо ) ¦--* ( s', $, $) & s' О F }
Чтобы лучше представить себе работу магазинного автомата, рассмотрим два примера. Пусть задан магазинный автомат М1 в следующем виде:
- М1: P = {a , b}; S = {s0 , s1 , s2}; H = {h0 , a}; F = {s0};
- f (s0 , a , h0) = (s1 , h0a),
f (s1 , a , a) = (s1 , aa),
f (s1 , b , a) = (s2 , $),
f (s2 , b , a) = (s2 , $),
f (s2 , e
, h0) = (s0 , $).
Этот автомат является детерминированным, поскольку каждому набору аргументов соответствует единственное значение функции. Работу автомата при распознавании входной цепочки aabb можно представить в виде последовательности конфигураций:
(s0,aabb,h0) |-- (s1,abb,h0a) |-- (s1,bb,h0aa) |-- (s2,b,h0a) |-- (s2,$,h0) |-- (s0,$,$) .
Нетрудно проверить, что при задании входной цепочки aabbb автомат не сможет закончить работу. Следовательно эта цепочка не принадлежит языку, допускаемому автоматом M1.
Магазинный автомат М2, заданный следующим описанием:
- М2: P = {a , b}; S = {s0, s1 , s2}; H = {h0, a , b}; F = {s2};
- (1)f (s0 , a , h0) = (s0, h0a),
(2)f (s0 , b , h0) = (s0, h0b),
(3) f (s0 , a , a) = {(s0,aa) , (s1 , $)},
(4) f (s0 , b , a) = (s0,ab),
(5) f (s0 , a , b) = (s0 , ba),
(6) f (s0 , b , b) = {(s0 , bb) , (s1 , $)},
(7) f (s1 , a , a) = (s1, $),
(8) f (s1 , b , b) = (s1, $),
(9) f (s2 , e
, h0) = (s2 , $),
является недетерминированным автоматом, поскольку одному и тому же набору аргументов, например (sо , a, a), соответствуют два значения функции.
Работу автомата рассмотрим для входной цепочки 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.
В общем случае справедливо следующее утверждение.
Пред.Страница
След.Страница Раздел Содержание
