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

UptoLike

ВУЗ: 

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

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

Рубрика: 

70
Кроме того, будет доказана основная теорема о том, что язык принимается
недетерминированным МП-автоматом тогда и только тогда, когда он является
КС-языком. Известно, что класс языков, принимаемых детерминированными
МП-автоматами, является строгим подклассом языков, принимаемых недетер-
минированными МП-автоматами.
§ 5.2. Формальное определение
Определение 5.1. Недетерминированный магазинный автомат (npda
nondeterministic push-down automaton) есть формальная система M =(Q, Σ, Γ, δ,
q
0
, Z
0
, F), где Q — конечное множество состояний, Σ — конечный входной
алфавит, Γ — конечный магазинный алфавит, δ — отображение типа
Q × (Σ∪{ε}) ×Γ→2
Q×Γ
*
, представляющее конечное управление автомата,
q
0
∈Q — начальное состояние, Z
0
∈Γ — начальный символ магазина, который в
самом начале является единственным содержимым магазина, F ⊆ Q —
множество конечных состояний.
Мы будем придерживаться следующей системы обозначений: строчные
буквы из начала латинского алфавита — отдельные входные символы;
строчные буквы из конца латинского алфавита служат для обозначения
цепочек входных символов; строчные греческие буквы — цепочки магазинных
символов; прописные латинские буквы — отдельные магазинные символы.
Определение 5.2. Для описания движений МП-автомата будем использо-
вать
понятие конфигурации, под которой будем подразумевать тройку (q, x, α),
где q∈Q — текущее состояние управления; x ∈Σ
*
— непросмотренная часть
входной цепочки (от текущего символа до её конца); α∈Γ
*
— магазинная
цепочка, причём крайний левый её символ считается находящимся на вершине
магазина.
Начальная конфигурация есть (q
0
, x, Z
0
), где x — вся входная цепочка.
Конечная конфигурация определяется по-разному в зависимости от того, какой
признак приёма используется. Если приём определяется при конечном
состоянии, то конечная конфигурация есть (q, ε, α) , где q∈F — автомат достиг
конечного состояния; ε означает, что вся входная цепочка прочитана; α∈Γ
*
—
произвольная магазинная цепочка. Достижение конечного состояния не
означает завершения работы автомата, а сигнализирует лишь о том, что
прочитанная к этому моменту часть входной цепочки принимается. За время
сканирования входной цепочки конечные состояния могут достигаться
несколько раз. Если приём определяется при пустом магазине, то конечная
конфигурация есть (q, ε, ε), где q∈Q — любое состояние; ε во второй позиции
означает, как и в предыдущем случае, что вся входная цепочка прочитана; ε в
третьей позиции означает, что магазин пуст. При пустом магазине никакое
дальнейшее движение не определено.
Запись δ(q, a, Z)={(p
1
, γ
1
), (p
2
, γ
2
),..., (p
m
, γ
m
)}, где q, p
i
∈Q, a∈Σ, Z∈Γ,
γ
i
∈Γ
*
(i = 1, 2,..., m), означает, что магазинный автомат в состоянии q с
символом a на входе и символом Z на вершине магазина может для любого i
перейти в состояние p
i
, заменить Z на γ
i
и продвинуться на входе к следующей
позиции (при этом крайний левый символ γ
i
окажется на вершине магазина,
если γ
i
≠ ε).

Страницы