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

UptoLike

ВУЗ: 

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

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

Рубрика: 

73
верхнего символа R магазина без продвижения по входной цепочке и переход в
состояние q
2
.
Магазинный автомат из примера 5.2 является детерминированным в том
смысле, что из любой конфигурации возможно не более одного движения.
Определение 5.5. Магазинный автомат M =(Q, Σ, Γ, δ, q
0
, Z
0
, F) называется
детерминированным (dpda
deterministic push-down automaton), если
1) для любых q∈Q, Z∈Γ и a∈(Σ∪{ε}) значение #δ(q,
a, Z) ≤ 1;
2)
для любых q ∈Q и Z∈Γ всякий раз, как δ(q, ε, Z) ≠∅, значение δ(q, a, Z)= ∅
для всех a∈Σ.
Условие 1 означает, что если движение определено, то оно единственно.
Условие 2 предотвращает выбор между ε-движением и движением,
использующим входной символ.
Для конечных автоматов детерминированная и недетерминированная
модели эквивалентны по отношению к распознаваемым языкам (см. теорему
3.4). Далее мы увидим, что это не так для МП-автоматов. Действительно, язык,
состоящий
из цепочек вида ww
R
, принимается недетерминированным pda, но не
существует никакого детерминированного pda, который распознавал бы такой
язык.
§ 5.3. Недетерминированные магазинные автоматы
и контекстно-свободные языки
Теперь докажем фундаментальный результат: класс языков, принимаемых
недетерминированными МП-автоматами, есть в точности класс контекстно-
свободных языков. Для этого сначала покажем, что множества языков,
принимаемых недетерминированными МП-автоматами при конечном
состоянии и при пустом магазине, совпадают, а затем, что класс языков,
принимаемых недетерминированными МП-автоматами при пустом магазине,
совпадают с классом языков, порождаемых контекстно-свободными грам-
матиками.
Теорема 5.1. Язык L = N(M), где M
некоторый недетерминированный
магазинный автомат,
тогда и только тогда, когда L = Т(M
’
) для некоторого
недетерминированного магазинного автомата M
’
.
Доказательство.
I. Необходимость. Пусть M =
(Q, Σ, Γ, δ, q
0
, Z
0
, ∅) — недетерминирован-
ный pda, такой, что L = N(M).
Положим M
’
= (Q ∪ {
0
q
'
, q
f
}, Σ, Γ∪{X}, δ′,
0
q
'
, X, {q
f
}), где δ′
определяется
следующим образом:
1) δ′
(
0
q
'
, ε, X)={(q
0
, Z
0
X)};
2) δ′
(q, a, Z) = δ(q, a, Z) для всех q∈Q, a ∈(Σ ∪ {ε}) и Z∈Γ;
3) δ′
(q, ε, X) = {(q
f
, ε)} для всех q∈Q.
Правило 1 воспроизводит начальную конфигурацию автомата M. При этом
начальный символ магазина X остаётся в качестве своеобразного маркера дна
магазина до тех пор, пока он не будет удалён последним движением автомата M
’
.

Страницы