Допустимость в МП-автоматах

3 основных принципа МП-автоматов:

1) если последовательность конфигураций является допустимой то вычисление образованное путем дописывания одной и той же цепочки к концам входных цепочек всех конфигураций также допустимо; 2) если вычисление допустимо, то вычисление образованное дописыванием одних и тех же магазинных символов внизу магазина для каждой конфигурации также допустимо; 3) если вычисление автомата допустимо и в результате некоторый суффикс входной цепочки не прочитан, то вычисление полученное удалением этого суффикса из входных цепочек каждой конфигурации также допустимо.

Теорема: P=(Q, ∑, G, d, q₀, Z₀, F) (q,w,α)├(p,v,β) тогда для "y=∑*, "gÎГ* справедливо (q,wy,αg)├(p,vy,βg). Эта теорема соответствует 1-2 утверждениям.

Теорема: если (y,wy,α)├(p,vy,β), то (q,w,α)├(p,v,β)

Допускающим МП по заключительному состоянию называется множество цепочек таких что (МП-автомат допускает свой вход, прочитывая его и достигая заключительного состояния):

L(P)={w | (q₀,w,Z₀)├(f,e,α),fÎF}

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

LN(P)={w | (q₀,w,Z₀)├(q,e,e)}, где q-произвольное состояние. Таким образом N(P) представляет собой мн-во входов w, которые Р может прочитать, одновременно опустошив свой магазин.

Эти два метода эквивалентны в том смысле, что для языка L найдется МП-автомат, допускающий его по заключительному состоянию ó когда для L найдется МП-автомат допускающий его по пустому магазину.

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

Теорема: если язык L является допустимым для некоторого автомата по допускающему состоянию, то существует автомат, в котором этот же язык допускается по пустому символу.

Эквивалентность МП-автоматов и КС-грамматик

Будем рассматривать левые порождения для КС-грамматик и автоматы допускающие по пустому магазину. Определим правила построения автомата для данной КС-грамматики: пусть дана грамматика G={T,V,Q,S}. Построим автомат P={{q},V,VÈT,d,q,S}.

d(q,e,A)={(q,b)|A→b}, где А-нетерминальный символ. d(q,а,а)=(q,e), где а-терминальный символ.

Теорема: МП-автомат, построенный по вышеописанному алгоритму допускает тот же язык что и грамматика.

Теорема(обратная): пусть существует МП-автомат, допускающий язык по пустому магазину. Тогда существует КС-грамматика имеющая этот же язык. Пусть есть автомат (∑,N,Q,d,q₀,Z₀), тогда построим грамматику (∑,V,R,S). Мн-во нетерминалов состоит из след. элементов: спец. символа S (стартовый) и символов [pXq], где p и q-символы произвольных состояний, а Х-магазинный символ. Мн-во продукций R состоит из продукций вида: S→[q₀,Z₀,p], где р-произвольное состояние. Если в автоматах есть d(q,a,Y)=(r,y₁,y₂,…,y_n), YÎN, aÎ∑È{e}. Тогда определяется правило вида [qYr]→a[qy₁r₁] [r₁y₂r₂]… [r_n-1y_nr] для всех возможных наборов r₁,…,r_n-1,r

Детерминированные автоматы с магазинной памятью.

МП-автомат будем называть детерминированным если для каждой тройки (q,a,X), где q-мн-во состояний, qÎQ, aÎTÈ{e}, xÎN.

d(q,a,X) принимает не более одного значения.

Язык L имеет префиксное свойство ó когда в нем нет 2 цепочек, одна из которых является префиксом другой.

Теорема: язык L является LN(P)-языком автомата P ó когда L обладает свойствами префикса и существует ДМП-автомат Р’, такой что L=L(P’).

Автоматы ДМП по заключительному состоянию допускают все регулярные языки и существуют КС-грамматики, которые не допускают такие автоматы.

Теорема: если некоторый язык является LN-языком для ДМП-автомата, то L имеет однозначную грамматику.

Если L является LP языком для некоторого автомата Р, то L имеет однозначную КС-грамматику.