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

UptoLike

ВУЗ: 

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

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

Рубрика: 

141
В частности, если a = ε, то выбор действия не зависит от текущего входного
символа и, как уже отмечалось, входная головка неподвижна. Если γ
i
= ε, то
верхний символ магазина стирается. Если y
i
= ε, то на выходную ленту ничего
не пишется, и её головка остаётся на прежнем месте.
В начальный момент q = q
0
, в магазине находится единственный символ Z
0
,
входная головка сканирует первый входной символ, а выходная лента пуста,
причём её головка находится на первой ячейке.
Работу магазинного преобразователя опишем в терминах конфигураций.
Определение 1.8. Конфигурацией магазинного преобразователя P назовем
четверку (q, x, α, y), где q ∈Q — текущее состояние, x ∈Σ
*
— часть входной
ленты от текущего символа до конца, называемая непросмотренной частью
входной цепочки, α∈Γ
*
— содержимое магазина (будем считать, что первый
символ цепочки α есть верхний символ магазина), y ∈∆
*
— содержимое
выходной ленты. Начальная конфигурация есть (q
0
, x, Z
0
, ε), где x обозначает
всю входную цепочку, а ε представляет выходную цепочку, которая пуста.
Пусть (q, ax, Zα, y) — текущая конфигурация и (p, γ, z) ∈δ(q, a, Z). Тогда
один такт работы pdt P записывается как отношение между двумя
последовательными конфигурациями: (q, ax, Zα, y) (p, x, γα, yz). Здесь q ∈Q,
a ∈Σ∪{ε}, x ∈Σ
*
, Z ∈Γ, α,γ∈Γ
*
, y,z ∈∆
*
.
Как обычно, определяются степень , транзитивное замыкание и
рефлексивно-транзитивное замыкание этого отношения.
Определение 1.9. Говорят, что y ∈∆
*
есть выход для x ∈Σ
*
при конечном
состоянии, если (q
0
, x, Z
0
, ε) (q, ε, α, y) для некоторых q ∈F и α∈Γ
*
.
Трансляция, определяемая магазинным преобразователем P при конечном
состоянии, есть τ(P)={(x, y) | (q
0
, x, Z
0
, ε) (q, ε, α, y) для некоторых q ∈F и
α∈Γ
*
}.
Говорят, что y ∈∆
*
есть выход для x ∈Σ
*
при пустом магазине, если
(q
0
,x, Z
0
,ε) (q, ε, ε, y) для некоторого q ∈Q.
Трансляция, определяемая магазинным преобразователем P при пустом
магазине, есть τ
e
(P)={(x, y) | (q
0
, x, Z
0
, ε) (q, ε, ε, y) для некоторого q ∈Q}.
Пример 1.3. Пусть P =({q},
{a, +,
*
}, {E, +,
*
}, {a, +,
*
}, δ, q, E, {q}), где
1) δ(q, a, E)={( q, ε, a)},
2) δ(q, +, E)={( q, EE+, ε)},
3) δ(q,
*
, E)={( q, EE
*
, ε)},
4) δ(q, ε, +) = {( q, ε, +)},
5) δ(q, ε,
*
)={( q, ε,
*
)}.
Рассмотрим действия pdt P на входе +
*
aaa:
(q, +
*
aaa, E, ε) (q,
*
aaa, EE+, ε) (q, aaa, EE
*
E+, ε) (q, aa, E
*
E+, a)
(q, a,
*
E+, aa) (q, a, E+, aa
*
) (q, ε, +, aa
*
a) (q, ε, ε, aa
*
a+).
k
−
−
+
−−
*
−
−
*
−−
*
−
−
*
−−
−
−
*
−
−
−
−
−
−
−
−
−− −−
−
−
−
−
−
−

Страницы