23. Автоматы с магазинной памятью (мпа). Формальное представление. Принципы функционирования.

Магазинный автомат – это, по существу, недетерминированный автомат с ε-переходами и одним дополнением – магазином, в котором хранится цепочка «магазинных символов». Присутствие магазина говорит о том, что магазин может хранить бесконечное количество информации. Однако отличие является работа по принципу FIFO (последний вошел - первый вышел). Поэтому МП автоматы могут распозновать, только КС-языки.

Виды: Допускает цепочку при попадании в допускающее состояние; допускает цепочку при опустошении стека независимо от состояния

Принцип работы:

1. Прочитывает и пропускает входной символ, используемый при переходе. Если в качестве входа используется ε, то входные символы не пропускаются.

2. Переходит в новое состояние, которое может и не отличаться от предыдущего.

3. Заменяет символ на вершине стека некоторой цепочкой. Цепочкой может быть ε, что соответствует снятию с вершины стека. Это может быть тот же символ, что хранился ранее на вершине. Автомат может заменить магазинный символ, что равносильно изменению вершины. Наконец символ может быть заменен цепочкой.

МП автомат записывается следующим образом:

P=(Q, ∑, Г, δ, q₀, Z_0, F), где Q – множество состояний, ∑ - алфавит , Г – магазинный алфавит, δ – функция переходов, q₀ начальное состояние, Z_{0 ­}–символ пустого магазина _, F - множество допустимых состояний.

Функция перходов

δ (q, σ, γ)=(p, γ')

Зададим автомат

S=({q₁,q₂,q_доп},{0,1},{0,1,Z₀}, δ, q₁,{ q_доп })

1. δ (q₁, 0, Z₀)={( q₁, 0Z₀)}; δ (q₁, 1, Z₀)={( q₁, 1Z₀)}

2. δ (q₁, 0, 0)={( q₁, 00)}; δ (q₁, 0, 1)={( q₁, 01)}

3. δ (q₁, ε, Z₀)={( q₂, Z₀)}; δ (q₁, ε, 0)={( q₂, 0)}; δ (q₁, ε, 1)={( q₁, 1)}

4. δ (q₁, 0, 0)={( q₂, ε)}; δ (q₁, 1, 1)={( q₂, ε)}

5. δ (q₂, ε, Z₀)={( q_доп, Z₀)}

При своей работе магазин переходит от одной конфигурации к другой. В конфигурацию входят его состояния (начальное, текущее, содержание магазина)

24. Язык мпа.

Класс языков допускаемых МП-автоматами являются контекстно-допустимыми. Для любого МП-автомата можно определить язык, который будет допускаться либо по пустому магазину, либо по попаданию в допускающее состояние. Для языка L найдется МП-автомат допускающий его по допускающему состоянию т. и т.т., когда существует некий МП-автомат допускающий его по пустому магазину. Возможно и их взаимное преобразование.

L_D={ω/(q₀, ω, Z₀)├─ (q, ε, α)}, q принадлежит F, α принадлежит Г

L_D={ω/(q₀, ω, Z₀)├─ (q, ε, ε)}, q принадлежит Q

Теорема: Если язык L, есть язык допустимый по опустошению магазина для некоторого МП-автомата (со всеми его параметрами)

P_N=(Q, ∑, Г, δ_N, q₀, Z_0, F), то существует такой МП-автомат который допускает этот же язык по допускающему состоянию.

Доказательство:

Введем некоторый символ X₀, который не принадлежит Г,

P_F=(Q, ∑, Г, δ_N, q₀, X_0, F), и дополнительно введем 2 состояния

1. δ₁ (p₀, ε, X₀)={ (q₀, Z₀X₀)}

2. Для всех состояний q из Q, входов α из ∑ и и магазинных символов γ из Г, δ_F (q, α, γ) содержит все пары из δ_N (q, α, γ)

3. δ₁ (q, ε, X₀) содержит (p_f, ε) для всех q из Q

Достаточность:

Необходимость:

Любое вычисление в автомате P_F, допускающее цепочку должно выглядеть как последовательность вычислений.

- есть вычисления в P_N

В результате, за исключением первого и последнего состояний вычисления ведутся на P_N, что позволяет сделать запись

Добавляется переход по пустому символу из каждого допускающего состояния автомата в некоторое состояние p.