Языки и трансляции. Мартыненко Б.К. - 73 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

72
Правила 1–6 позволяют pda M запомнить входной символ в магазинной
памяти. При этом входной символ 0 отображается магазинным символом B, а
символ 1 символом G на вершине магазина.
Правила 3 и 6 предоставляют автомату выбор движений между
запоминанием очередного входного символа в магазине (в предположении, что
середина входной цепочки не достигнута) и переходом в режим сопоставления
текущего входного символа с символом на вершине магазина и стиранием
последнего в случае их соответствия (в предположении, что достигнута
середина входной цепочки).
Если на входе находится цепочка вида ww
R
, то существует такая
последовательность движений, которая опустошает магазин к моменту
достижения конца цепочки. Например, если на вход поступает цепочка 0110, то
автомат имеет выбор движений, представленный на рис. 5.1, где приведено
дерево возможных переходов между конфигурациями. Существующая среди
них следующая последовательность движений:
(q
1
, 0110, R) (q
1
,
110, BR) (q
1
,
10, GBR) (q
2
,
0, BR) (q
2
,
ε
, R) (q
2
,
ε
, ε)
даёт основание заключить, что входная цепочка 0110 принимается.
Рис. 5.1.
Пример 5.2. Пусть pda M = ({q
1
, q
2
}, {0, 1, c}, {R, B, G}, δ, q
1
, R, ∅), где
1) δ(q
1
, 0, R) = {(q
1
, BR)}, 7) δ(q
2
, 0, B) = {(q
2
, ε)},
2) δ(q
1
, 0, B) = {(q
1
, BB)}, 8) δ(q
2
, ε, R) = {(q
2
, ε)},
3) δ(q
1
, 0, G) = {(q
1
, BG)}, 9) δ(q
2
, 1, G) = {(q
2
, ε)},
4) δ(q
1
, c, R) = {(q
2
, R)}, 10) δ(q
1
, 1, R) = {(q
1
, GR)},
5) δ(q
1
, c, B) = {(q
2
, B)}, 11) δ(q
1
, 1, B) = {(q
1
, GB)},
6) δ(q
1
, c, G) = {(q
2
, G)}, 12) δ(q
1
, 1, G) = {(q
1
, GG)}.
Легко сообразить, что N(M)={wcw
R
|w∈{0,1}
*
}, где w
R
обозначает инвер-
тированную цепочку w.
Рассмотрим движения pda
M при наличии цепочки 01с10 на его входе:
(q
1
, 01с10, R)
__
M
(q
1
, 1с10, BR)
__
M
(q
1
, с10, GBR)
__
M
(q
2
, 10, GBR)
__
M
__
M
(q
2
, 0, BR)
__
M
(q
2
, ε, R)
__
M
(q
2
, ε, ε).
Следовательно, цепочка 01с10 принимается при пустом магазине. Заметим,
что равенство δ(q
2
, ε, R)={(q
2
, ε)} означает движение, не зависящее от входного
символа, каким бы он ни был, — в любом случае происходит стирание
(q
1
, 10, GBR)
(q
2
, ε, ε)
(q
2
, ε, R)
(q
1
, ε, BGGBR)
(q
1
, 0, GGBR)
(q
1
, 110, BR)
(q
2
, 0, BR)
(q
2
, 0110,
ε
)
(q
1
, 0110, R)
−−
−−
−
−
−
−
−−

Страницы