Допустимость в МП-автоматах
3 основных принципа МП-автоматов:
1) если последовательность конфигураций является допустимой то вычисление образованное путем дописывания одной и той же цепочки к концам входных цепочек всех конфигураций также допустимо; 2) если вычисление допустимо, то вычисление образованное дописыванием одних и тех же магазинных символов внизу магазина для каждой конфигурации также допустимо; 3) если вычисление автомата допустимо и в результате некоторый суффикс входной цепочки не прочитан, то вычисление полученное удалением этого суффикса из входных цепочек каждой конфигурации также допустимо.
Теорема: P=(Q, ∑, G, d, q0, Z0, 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 | (q0,w,Z0)├(f,e,α),fÎF}
язык допустимый по пустому магазину ( для любого МП-автомата мы можем определить язык «допускаемый по пустому магазину», т.е. мн-во цепочек, приводящих МП-автомат в начальной конфигурации к опустошению магазина):
LN(P)={w | (q0,w,Z0)├(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,q0,Z0), тогда построим грамматику (∑,V,R,S). Мн-во нетерминалов состоит из след. элементов: спец. символа S (стартовый) и символов [pXq], где p и q-символы произвольных состояний, а Х-магазинный символ. Мн-во продукций R состоит из продукций вида: S→[q0,Z0,p], где р-произвольное состояние. Если в автоматах есть d(q,a,Y)=(r,y1,y2,…,yn), YÎN, aÎ∑È{e}. Тогда определяется правило вида [qYr]→a[qy1r1] [r1y2r2]… [rn-1ynr] для всех возможных наборов r1,…,rn-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 имеет однозначную КС-грамматику.