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

UptoLike

ВУЗ: 

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

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

Рубрика: 

71
Пусть текущая конфигурация имеет вид: (q, ax, Zα), где x∈Σ
*
. В терминах
конфигураций одно из возможных движений представляется следующим
образом: (q, ax, Zα) (p
i
, x, γ
i
α) для любого i, 1 ≤ i ≤ m.
Запись δ(q, ε, Z)={(p
1
, γ
1
), (p
2
, γ
2
),..., (p
m
, γ
m
)} означает, что pda в состоянии
q независимо от того, какой символ на входе, и с символом Z на вершине
магазина может для любого i перейти в состояние p
i
, заменить Z на γ
i
, не
изменяя текущей позиции на входе.
Пусть текущая конфигурация имеет вид (q, x, Zα). Тогда в терминах конфи-
гураций одно из возможных движений представляется следующим образом:
(q, x, Zα)
__
(p
i
, x, γ
i
α) для любого i, 1 ≤ i ≤ m.
Если γ
i
= ε, то происходит стирание верхнего символа магазина — вершина
магазина опускается; если |γ
i
| =1, то происходит замена верхнего символа
магазина; если |γ
i
| >1, то вершина магазина поднимается.
Таким образом, мы ввели на множестве конфигураций pda отношение
непосредственного следования одной конфигурации за другой, использовав
для него символ .
Естественно ввести степень отношения , транзитивное замыкание
и
рефлексивно-транзитивное замыкание этого отношения на множестве
конфигураций. При необходимости явно показать, движения какого pda рас-
сматриваются, под соответствующими значками указывается имя автомата,
например:
__
M
,
__
M
n
,
__
M
+
или
*
__
M
. Напомним, что содержательно эти значки
обозначают переход от конфигурации, стоящей слева от значка, к
конфигурации, стоящей справа от значка, соответственно за одно движение, за
n движений, за положительное число движений, за произвольное, может быть
нулевое, число движений.
Определение 5.3. Язык, принимаемый магазинным автоматом
M =(Q, Σ, Γ, δ, q
0
, Z
0
, F ) при конечном состоянии, определим как множество
T(M)={w ∈Σ
*
|( q
0
, w, Z
0
) (q, ε, α), q∈F}.
Определение 5.4 Язык, принимаемый магазинным автоматом
M =(Q, Σ, Γ, δ, q
0
, Z
0
, F ) при пустом магазине, определим как множество
N(M)=
{w∈Σ
*
|( q
0
, w, Z
0
) (q, ε, ε), q∈Q}. В этом случае неважно, каким
является множество конечных состояний, и часто оно просто считается
пустым.
Пример 5.1. Пусть pda M = ({q
1
, q
2
}, {0, 1}, {R, B, G}, δ, q
1
, R, ∅), где
1) δ(q
1
, 0, R)={(q
1
, BR)}, 6) δ(q
1
, 1, G) = {(q
1
, GG), (q
2
, ε)},
2) δ(q
1
, 1, R) = {(q
1
, GR)}, 7) δ(q
2
, 0, B) = {(q
2
, ε)},
3) δ(q
1
, 0, B) = {(q
1
, BB), (q
2
, ε)}, 8) δ(q
2
, 1, G) = {(q
2
, ε)},
4) δ(q
1
, 0, G) = {(q
1
, BG)}, 9) δ(q
1
, ε, R)={(q
2
, ε)},
5) δ(q
1
, 1, B) = {(q
1
, GB)}, 10) δ(q
2
, ε, R) = { q
2
, ε)}.
M — недетерминированный магазинный автомат, принимающий язык
N(M) =
{ww
R
|w∈{0, 1}
*
}, где w
R
обозначает инвертированную цепочку w, при
пустом магазине.
__
n
__
+
*
__
__
*
__
*
__
__

Страницы