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