Изменения

Далее будут приведены конструкции для построения МП-автомата по заданной КС-грамматике, и наоборот. Также будет приведена теорема об эквивалентности языков, задаваемых ими.=== Построение МП-автомата по заданной КС-грамматике ===Пусть <tex> G=(V,T,Q,S) </tex> — КС-грамматика. Построим МП-автомат <tex> P=(\{q\},T,V \cup T, \delta ,q,S) </tex>, который допускает <tex> L(G) </tex> по пустому магазину. Функция переходов <tex> \delta </tex> будет определена по следующим правилам:*1. <tex> \delta(q,\varepsilon,A)=\{(q,\beta )| A \rightarrow \beta</tex> — продукция <tex> G \} </tex> для каждой переменной <tex> A </tex>. *2. <tex> \delta(q,a,a)=\{(q,\varepsilon)\} </tex> для каждого терминала <tex> a </tex>.

{{Теорема|id =th1|statement === Пример ====Преобразуем грамматику выражений в Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | контекстно-свободных языков]] <tex>(\mathrm{CFG})</tex> является подмножеством класса языков, задаваемых [[Автоматы с магазинной памятью | автоматами с магазинной памятью]] <tex>(\mathrm{PDA})</tex>, то есть по любой КС-грамматике можно построить МП-автомат, задающий тот же язык, что и исходная грамматика. |proof = Пусть дана КС-грамматика:<tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex>. Поскольку классы языков, допускаемых МП-автоматами по допускающему состоянию и по пустому стеку, [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность | совпадают]], достаточно построить автомат с допуском по пустому стеку. *Построим автомат из одного состояния <tex>q</tex> с входным алфавитом <tex>\Sigma</tex>, стековым алфавитом <tex>N \cup \Sigma</tex>, маркером дна <tex>S</tex> и функцией перехода <tex>\delta</tex>, определённой ниже. Формально <tex>A = \langle \Sigma, N \cup \Sigma, \{q\}, q, S, \delta \rangle</tex>, где <tex> I \rightarrow adelta</tex> задаётся следующим образом: [[Файл:Delta.png |bthumb |I1right |I0|Ia|Ib Добавим такие переходы для каждого терминала <tex>a</tex> и правила вывода <tex>V \rightarrow \gamma</tex>,]] *для каждого правила вывода <tex> E V \rightarrow I|E\gamma \in P</tex> определим <tex>\delta(q, \varepsilon, V) = \{(q, \gamma)\}</tex>;*E|E+E|для каждого терминала <tex>a</tex> определим <tex> \delta(q, a, a) = \{(Eq, \varepsilon) \} </tex>.Множеством входных символов является Покажем, что язык, допускаемый автоматом <tex>A</tex>, совпадает с языком грамматики <tex>\Gamma</tex>, то есть что <tex>S \Rightarrow^* w \iff (q, w, S) \vdash^* (q, \varepsilon, \varepsilon)</tex>: ;Пусть <tex>S \Rightarrow^* w</tex>.: Рассмотрим [[ Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | левосторонний вывод ]] <tex>S = \gamma_0 \Rightarrow \gamma_1 \Rightarrow ... \Rightarrow \gamma_n=w</tex>. Обозначим как <tex>v_i</tex> наибольший префикс <tex>\gamma_i</tex>, состоящий только из терминалов, а <tex> \alpha_i</tex> {{a---}} остаток <tex>\gamma_i</tex>,bто есть <tex>\gamma_i = v_i\alpha_i</tex>,1причём <tex>v_i \in \Sigma^*</tex>,0а <tex>\alpha_i</tex> начинается с нетерминала (либо пустая). С помощью индукции по <tex>i</tex> докажем,что <tex>(q, w,S)\vdash^* (q,+x_i,*\alpha_i)</tex> для <tex>i \leq n</tex>, где <tex>x_i</tex> {{---}} то, что остаётся после чтения <tex>v_i</tex>, то есть <tex>v_ix_i = w</tex>. Эти символы вместе с переменными Иными словами, переходя по автомату по символам <tex>v_i</tex> I,E можно оставить на стеке <tex>\alpha_i</tex> образуют магазинный алфавит. Функция переходов определена следующим образом:* '''База:''' <br> Пусть <tex>i = 0</tex>. <br> В этом случае <tex>\gamma_0 = S</tex>, поэтому <tex>v_0 = \varepsilon, \alpha_0 = S, x_i = w</tex>. Очевидно, <tex>(q, w, S) \vdash^* (q, w, S)</tex>.:* '''Индукционный переход:''' <br> Пусть <tex>(q, w, S) \vdash^*a(q, x_i, \alpha_i)</tex> для <tex>i < n</tex>. <tex>\alpha_i</tex> по определению начинается с какого-то нетерминала <tex>V</tex> (если <tex>\alpha_i = \varepsilon</tex>, то получена <tex>\gamma_n</tex>, а мы предположили, что <tex>i < n</tex>) , то есть <tex>\alpha_i = Vq_i</tex> Поскольку мы рассматриваем левосторонний вывод, то переход <tex>\gamma_i \Rightarrow \gamma_{i + 1}</tex> включает замену нетерминала <tex>V</tex> на какую-то цепочку <tex>\beta</tex> по правилу <tex>V \rightarrow \beta</tex>. Так как <tex>\gamma_i = v_i \alpha_i = v_i V q_i</tex>, то <tex>\gamma_{i + 1} = v_i \beta q_i = v_{i + 1} \alpha_{i + 1}</tex>. В автомате <tex>A</tex> по построению присутствует правило перехода <tex> \delta(q,\varepsilon,IV)=\{(q,a\beta)\}</tex>, поэтому <tex>\alpha_i</tex> на стеке можно заменить на <tex>\beta q_i</tex>. Заметим, что <tex>\beta q_i</tex> представляет собой конкатенацию нескольких терминалов из <tex>w</tex> и <tex>\alpha_{i + 1}</tex>. Считывая очередные символы строки <tex>w</tex>, будем переходить по автомату, убирая терминалы со стека, пока не встретим нетерминал. Таким образом, на стеке окажется <tex>\alpha_{i+1}</tex>. Получили, что <tex>(q,bx_i, \alpha_i)\vdash^* (q, x_{i + 1}, \alpha_{i + 1})</tex>, а значит, <tex>(q,Iaw, S), \vdash^* (q,Ibx_{i + 1}, \alpha_{i + 1})</tex>. Индукционный переход доказан.: Заметим, что <tex>\alpha_n = \varepsilon, v_n = w, x_n = \varepsilon</tex>, поэтому <tex>(q,I0w, S), \vdash^* (q,I1\varepsilon, \varepsilon)};</tex>. ;Пусть <tex>(q, w, S) \vdash^*b(q, \varepsilon, \varepsilon) </tex>.: Воспользуемся индукцией по числу переходов в автомате и докажем для любой строки <tex>x</tex> и нетерминала <tex>M \deltain N</tex>, что если <tex>(q, x, M) \vdash^* (q,\varepsilon,E\varepsilon)={</tex>, то <tex>M \Rightarrow^* x</tex>.:* '''База:''' <br> Пусть в автомате один переход. <br> Если <tex>(q,Ix, M), \vdash^* (q,E+E\varepsilon, \varepsilon)</tex>, (qто <tex>x = \varepsilon</tex> и в грамматике присутствует правило <tex>M \rightarrow \varepsilon</tex>,Eпо которому выводится <tex>\varepsilon = x</tex>.:*E'''Индукционный переход:''' <br> Предположим, что автомат <tex>A</tex> совершает <tex>n</tex> шагов (<tex>n > 1</tex>). Изначально на вершине стеке находится <tex>M</tex>, поэтому первый переход совершается по какому-то правилу из первого пункта построения <tex>\delta</tex>, и на стеке оказывается последовательность из терминалов и нетерминалов <tex>Y_1 Y_2 \ldots Y_k</tex>. В процессе следующих <tex>n - 1</tex> переходов автомат прочитает строку <tex>x</tex> и поочерёдно вытолкнет со стека <tex>Y_1 Y_2 \ldots Y_k</tex>. Разобьём <tex>w</tex> на подстроки <tex>x_1 x_2 \ldots x_k</tex>, где <tex>x_1</tex> {{---}} порция входа, прочитанная до выталкивания <tex>Y_1</tex> со стека, <tex>x_2</tex> {{---}} следующая порция входа, прочитанная до выталкивания <tex>Y_2</tex> со стека и так далее. Формально можно заключить, что <tex>(q,x_i x_{i + 1} \ldots x_k, Y_i) \vdash^* (E)q, x_{i + 1} \ldots x_k, \varepsilon)</tex>, причём менее чем за <tex>n</tex> шагов. Если <tex>Y_i</tex> {{---}} нетерминал, то по индукционному предположению имеем, что <tex>Y_i \Rightarrow^* x_i</tex>. Если же <tex>Y_i</tex> {{---}};терминал, то должен совершаться только один переход, в котором проверяется совпадение <tex>x_i</tex> и <tex>Y_i</tex>. Значит, <tex>Y_i \Rightarrow^* x_i</tex> за 0 шагов. <br> Таким образом, получаем, что <tex>M \Rightarrow Y_1 Y_2 \ldots Y_k \Rightarrow^* x_1 x_2 \ldots x_k = x</tex>.: Подставляя <tex>w</tex> вместо <tex>x</tex> и <tex>S</tex> вместо <tex>M</tex>, получаем, что <tex>S \Rightarrow^*c) w.</tex>}} === Пример ===Поскольку доказательство теоремы конструктивно, то используя правила перехода, описанные в ней, можно преобразовать любую КС-грамматику в МП-автомат. Рассмотрим грамматику слов над алфавитом <tex>\{0, 1\}</tex>, в которых одинаковое количество нулей и единиц:: <tex> S \rightarrow 0S1 </tex>: <tex> S \rightarrow 1S0 </tex>: <tex> S \rightarrow \varepsilon </tex>Множеством терминалов является <tex>\Sigma = \{0, 1\}</tex>, а нетерминалов {{---}} <tex>N = \{S\}</tex>. Таким образом, стековый алфавит состоит из <tex>0, 1, S</tex>. Функция переходов <tex>\delta</tex> определена следующим образом: : <tex> \delta(q,a\varepsilon,aS)=\{(q, 0S1), (q, 1S0), (q,\varepsilon)\}</tex>; (в соответствии с первым пунктом построения <tex>\delta</tex>) : <tex> \delta(q,b0,b0)=\{(q,\varepsilon)\}</tex>;...<tex> \delta(q,*1,*1)=\{(q,\varepsilon)\}</tex>(в соответствии со вторым пунктом построения <tex>\delta</tex>) Получившийся автомат: [[Файл:Example1. Если входной png]] == Построение КС-грамматики по МП-автомату =={{Теорема|id = th2|statement = Класс языков, задаваемых автоматами с магазинной памятью <tex>(\mathrm{PDA})</tex>, является подмножеством класса контекстно-свободных языков <tex>(\mathrm{CFG})</tex>, то есть по любому МП-автомату можно построить КС-грамматику, задающую тот же язык, что и допускаемый автоматом.|proof = Пусть дан МП-автомат с допуском по пустому стеку <tex>A = \langle \Sigma, \Pi, Q, q_0 \in Q, z_0, \delta \rangle</tex>. Как отмечалось ранее, предположение о допуске по пустому стеку не умаляет общности. Построим эквивалентную ему КС-грамматику <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex>. В качестве нетерминалов будем использовать конструкции вида <tex>[pXq]</tex> (где <tex> p, q \in Q</tex>, <tex>X \in \Pi</tex>), которая неформально означает, что в процессе изменения состояния автомата от <tex>p</tex> до <tex>q</tex> символ совпадает <tex>X</tex> удаляется с вершиной вершины стека, не затрагивая то вершина удаляется, что находится ниже. Также введём стартовый нетерминал <tex>S</tex>. Таким образом, <tex>N = Q \times \Pi \times Q \cup S</tex>.Пункты '''Правила вывода <tex>P</tex> построим следующим образом: * для каждого состояния <tex>p \in Q</tex> добавим правило <tex>S \rightarrow [q_0 z_0 p]</tex>;* для каждого перехода <tex>(r_0, \gamma_1 \gamma_2 \ldots \gamma_k) \in \delta(p, a, X)</tex> сделаем следующее: для всех упорядоченных списков состояний <tex>[r_1, r_2 \ldots r_k] \in Q^k</tex> добавим правило <tex>[p X r_k] \rightarrow a [r_0 \gamma_1 r_1] [r_1 \gamma_2 r_2] \ldots [r_{k - 1} \gamma_k r_k]</tex>, если <tex>k > 0</tex>, и <tex>[p X r_0] \rightarrow a</tex>, если <tex>k = 0</tex>. Нетерминал <tex>[pXq]</tex> должен выводить только те строки <tex>w</tex>, которые переводят автомат из состояния <tex>(p,b''' образованы по первому правилу построения функции переходовX)</tex> в <tex>(q, \varepsilon)</tex>. Формально это можно записать следующим образом: <tex>[pXq] \Rightarrow^* w \iff (p, w, X) \vdash^* (q, \varepsilon, а пункт '''c''' по второму\varepsilon)</tex>.Докажем это утверждение:

==== Корректность построения ====;Пусть <tex>(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>.: Докажем, что <tex>[pXq] \Rightarrow^* w</tex>, используя индукцию по числу переходов в автомате.:*'''База:'''<br> Пусть выполняется только один переход.<br> Тогда длина <tex> w</tex> не больше единицы и <tex>(q, \varepsilon) \in L\delta(Gp, w, X)</tex>, тогда поэтому правило <tex>[pXq] \rightarrow w</tex> по построению должно присутствовать в <tex>P</tex>.:*'''Индукционный переход:'''<br> Предположим, что <tex> (p, w , X) \vdash^* (q, \varepsilon, \varepsilon)</tex> за <tex>n > 1</tex> шагов. Первый переход имеет следующее левое порождение:вид <tex>(p, w, X) \vdash (r_0, x, \gamma_1 \gamma_2 \ldots \gamma_k) \vdash^* (q, \varepsilon, \varepsilon)</tex>, где <tex> S w = ax</tex> (<tex>a</tex> {{---}} символ из <tex>\Sigma</tex> или <tex>\varepsilon</tex>). Значит, <tex>(r_0, \gamma_1 \Rightarrow gamma_2 \ldots \gamma_k) \in \delta(p, a, X)</tex>. По построению в грамматике должно присутствовать правило <tex>[p X r_k] \rightarrow a [r_0 \gamma_1 r_1] [r_1 \gamma_2 r_2] \ldots [r_{k - 1} \gamma_k r_k]</tex> для любой последовательности состояний <tex>[r_1, \Rightarrow ldots r_k]</tex>.Пусть <tex>x = w_1 w_2 \ldots w_k</tex>, где <tex>w_i</tex> {{---}} входная цепочка, которая прочитывается до удаления <tex>\gamma_i</tex> со стека, то есть найдётся такая последовательность состояний <tex>[r_1, \ldots r_k]</tex>, что <tex>(r_{i - 1}, w_i, \gamma_i) \vdash^* (r_i, \varepsilon, \varepsilon)</tex>, причём заканчивается всё в <tex>q = r_k</tex>.Заметим, что все эти выводы содержат менее <tex>n</tex> переходов, а значит, по индукционному предположению <tex>[r_{i - 1} \gamma_i r_i] \Rightarrow^* w_i</tex> для всех <tex>i</tex>. <br> Собирая вышесказанное, получаем <tex>[p X r_k] \Rightarrow a [r_0 \gamma_1 r_1] [r_1 \gamma_2 r_2] \ldots [r_{k - 1} \gamma_k r_k] \Rightarrow ^* a w_1 w_2 \gamma_nldots w_k = w</tex>. Так как <tex>r_k =q</tex>, то <tex>[pXq] \Rightarrow^* w</tex>, тем самым индукционный переход доказан.Покажем индукцией по ;Пусть <tex> i [pXq] \Rightarrow^* w</tex>.: Докажем, что <tex> (qp,w,SX)\vdash^*(q,y_i\varepsilon,\alpha_ivarepsilon)</tex>, используя индукцию по числу шагов в порождении.:*'''База:''' <br> Пусть <tex>[pXq] \Rightarrow^* w</tex> за один шаг. Очевидно<br> Тогда в <tex>\Gamma</tex> должно быть правило вывода <tex>[pXq] \rightarrow w</tex>, а значит, что в автомате должен быть переход <tex> (q,w,S\varepsilon)\vdash^*in \delta(qp,w,SX) </tex>и <tex>w</tex> не может иметь длину больше единицы.*Переход. ПредположимТаким образом, что <tex> (qp,w,SX)\vdash^*(q,w_i\varepsilon,\alpha_ivarepsilon) </tex>. Заметим:*'''Индукционный переход:''' <br> Предположим, что шаг порождения <tex> y_i [pXq] \Rightarrow^* w </tex> за <tex>n > 1</tex> шагов. По построению вывод должен иметь вид <tex>[p X r_k] \Rightarrow y_a [r_0 \gamma_1 r_1] [r_1 \gamma_2 r_2] \ldots [r_{i+k - 1}\gamma_k r_k] \Rightarrow^* w</tex> включает замену некоторой переменной , где <tex> A r_k = q</tex> ее продукцией и <tex> (r_0, \gamma_1 \gamma_2 \ldots \gamma_k) \in \beta delta(p, a, X)</tex>. Правило 1 построения МП-автомата позволяет на заменить Вновь представим <tex> A w</tex> на вершине стека на цепочку в виде <tex> w = a w_1 w_2 \beta ldots w_k</tex>так, а правило 2 позволяет затем сравнить любые терминалы на вершине со входными символами. В результате достигается МО что <tex> (q,y_[r_{i+- 1}\gamma_i r_i] \Rightarrow^* w_i</tex>. Так как все эти выводы содержат менее <tex>n</tex> шагов,\alpha_то по индукционному предположению для всех <tex>i</tex> выполнено <tex>(r_{i+- 1}, w_i, \gamma_i) \vdash^* (r_i, \varepsilon, \varepsilon) </tex>.Собирая всё вместе, получаем <tex>(r_0, w_1 w_2 \ldots w_k, \gamma_1 \gamma_2 \ldots \gamma_k) \vdash^* (r_1, w_2 w_3 \ldots w_k, \gamma_2 \gamma_3 \ldots \gamma_k) \vdash^* \ldots \vdash^*Также заметим(r_k, \varepsilon, что \varepsilon)</tex>. Так как <tex> (r_0, \gamma_1 \gamma_2 \ldots \gamma_k) \in \alpha_n delta(p, a, X)</tex> и <tex>r_k = q</tex>, то в итоге <tex>(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>.  Таким образом , мы доказали, что <tex> [pXq] \Rightarrow^* w \iff (qp,w,SX)\vdash^*(q,\varepsilon,\varepsilon) </tex>. Заметим, т.е допускает что <tex> P S \Rightarrow^* w</tex> по пустому стеку.{{Утверждение|about=1|statement= Если МП-автомат тогда и только тогда, когда найдётся <tex> P p</tex> построен по грамматике , что <tex> G [q_0 z_0 p] \Rightarrow^* w</tex>, с использованием указанной . По доказанному выше конструкцииэто равносильно тому, то что <tex> L(Gq_0, w, z_0) \subseteq Nvdash^* (Pp, \varepsilon, \varepsilon) </tex>|proof= Выше доказана корректность построения МП-автомата , то есть что <tex>A</tex> допускает <tex>w</tex> по любой КС-грамматикепустому стеку. Значит множество языков КС-грамматик является подмножеством языковСуммируя всё вышесказанное, получаем, что построенная грамматика <tex>\Gamma</tex> порождает слово <tex>w</tex> тогда и только тогда, допускаемых МП-автоматамикогда оно допускается автоматом <tex>A</tex>.

=== Построение КС-грамматики по МП-автомату Пример ===Наша конструкция эквивалентной грамматики использует переменные вида: Пусть у нас имеется МП-автомат <tex> [pXq]A = \langle \{i,e\}, \{Z\}, \{q\}, q, Z, \delta \rangle</tex> — которая означает, что в процессе изменения состояния автомата от функция <tex> p \delta</tex> до задана следующим образом::<tex> \delta(q, i, Z) = \{(q , ZZ)\}</tex>, :<tex> X \delta(q, e, Z) = \{(q, \varepsilon)\}</tex> удалилось из стека.<br>[[Файл:-pXq-.jpg]]

Следует отметить, что удаление <tex> X </tex> может являться результатом множества переходов.<br>Пусть <tex> P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0)</tex> — МП-автомат. Построим <tex> G=(V,\Sigma,R,S)</tex>, где <tex> V </tex> состоит из:*1 Специальный стартовый символ <tex> S </tex>,*2 Все символы вида <tex> [pXq]</tex>, где <tex> p </tex> и <tex> q </tex> — состояния из <tex> Q </tex>, а <tex> X </tex> — магазинный символ из <tex> \Gamma </tex>.Грамматика <tex> G </tex> имеет следующие продукции[Файл:*a) продукции <tex> S \rightarrow [q_0Z_0p] </tex> для всех <tex> p </tex>, таким образом <tex> (q,w,Z_0)\vdash^* (q,\varepsilon,\varepsilon)</tex>*b) пусть <tex> \delta(q,a,X) </tex> содержит <tex> (r,Y_1Y_2...Y_k)</tex>. Тогда для всех списков состояний <tex> r_1,r_2,.Example2..,r_k</tex> в грамматике <tex> G </tex> есть продукция <tex> [qXr_kpng]\rightarrow a[r Y_1 r_1][r_1 Y_1 r_2]...[r_{k-1} Y_k r_k]</tex>.==== Пример ====Пусть у нас имеется <tex> P=(\{q\},\{i,e\},\{Z\},\delta,q,Z)</tex>, функция <tex> \delta </tex> задана следующим образом:*<tex> \delta(q,i,Z)=\{(q,ZZ)\}</tex>,*<tex> \delta(q,e,Z)=\{(q,\varepsilon)\}</tex>.Так как стековый алфавит <tex> P A</tex> имеет содержит лишь один магазинный символ и одно состояние, то грамматика строится просто. У нас в построенной грамматике будет всего две переменныелишь 2 нетерминала: *a) <tex> S </tex> — стартовый символнетерминал. *b) <tex> [qZq] </tex> — единственная тройка, которую можно собрать из наших состояний автомата и магазинных символовстекового алфавита. Также грамматика имеет следующие продукцииправила вывода:*1. Единственной продукцией для <tex> S </tex> является <tex> S \rightarrow [qZq] </tex>. Но если бы у автомата было <tex> n </tex> состояний, то тут бы имелось и <tex> n </tex> продукций.*2. Из того факта, что <tex> \delta(q,i,Z) </tex> содержит <tex> (q,ZZ)</tex>, получаем продукцию правило вывода <tex> [qZq] \rightarrow i[qZq][qZq] </tex>. Если бы у автомата было '''<tex>n''' </tex> состояний, то такое правило порождало такой переход порождал бы <tex> n^2 </tex> продукций.*3. Из <tex> \delta(q,e,Z)=\{(q,\varepsilon)\} </tex> получаем продукцию правило вывода <tex> [qZq] \rightarrow \varepsilon e</tex>Для удобства тройку <tex> [qZq] </tex> можно заменить символом <tex> A </tex>, в таком случае грамматика состоит из следующих продукцийправила вывода в грамматике будут следующие:* :<tex> S \rightarrow A</tex>* :<tex> A \rightarrow iAA | </tex>:<tex>A \varepsilonrightarrow e</tex>В действительности можно заметитьУпростим грамматику, что заменив <tex>SA</tex> и на <tex>AS</tex> порождают одни и те же цепочки(очевидно, поэтому их можно обозначить одинаковоона не поменяется), итого: и получим в результате <tex> G\Gamma =(\langle\{Si,e\},\{i,eS\}, S,\{S \rightarrow iSS| e\}\rangle</tex> == Эквивалентность языков МП-автоматов и КС-языков=={{Теорема|about = об эквивалентности языков МП-автоматов и КС-языков|statement = Множество языков, допускаемых МП-автоматами, совпадает с множеством контекстно-свободных языков.|proof = [[#th1 | Первая теорема]] гласит, что <tex> \mathrm{CFG} \subseteq \mathrm{PDA} </tex>, а [[#th2 | вторая]] {{---}} что <tex> \varepsilonmathrm{PDA} \subseteq \mathrm{CFG}</tex>. Таким образом,S)<tex> \mathrm{PDA} = \mathrm{CFG} </tex>.}} == Следствия =={{Утверждение|statement = Для любого МП-автомата с допуском по пустому стеку существует эквивалентный МП-автомат с одним состоянием.|proof = Построим КС-грамматику по данному автомату, затем по полученной грамматике построим МП-автомат, как указано выше. Заметим, что этот автомат будет иметь одно состояние, что и требовалось доказать.}}

|about=2|statement= Если КСДля любого МП-грамматика <tex> G </tex> построена автомата с допуском по пустому стеку существует эквивалентный МП-автомату <tex> P </tex>, с использованием указанной выше конструкцииавтомат, то <tex> N(P) \subseteq L(G) </tex>в любом переходе которого на стек кладётся не больше двух символов.|proof= Выше доказана корректность построения Построим КС-грамматики грамматику по МП-данному автоматуи приведём её к [[Нормальная форма Хомского | нормальной форме Хомского]]. Значит языки допускаемые Затем по полученной грамматике построим МП-автоматами являются подмножеством языковавтомат, как указано выше. Заметим, заданных КС-грамматикойчто в нормальной форме Хомского правые части всех правил имеют длину не больше двух, поэтому в любом переходе в полученном автомате на стек кладётся не больше двух символов.

=== Эквивалентность языков МП-автоматов и КС-языков==={{ТеоремаУтверждение|aboutstatement = Об эквивалентности языков Для любого МП-автоматов и КС-языков|statement= Множество языков, допускаемых автомата существует эквивалентный МП-автоматами совпадает с множеством языков, задаваемых автомат с помощью контекстно-свободных грамматик.|proof= Из утверждения 1 следует, что допуском по пустому стеку без <tex> L(G) \subseteq N(P) varepsilon</tex>-переходов.|proof = Построим КС-грамматику по данному автомату, затем по полученной грамматике построим МП-автомат, в свою очередь из утверждения 2 следуеткак указано выше. Заметим, что этот автомат не будет иметь <tex> N(P) \subseteq L(G) </tex>. Отсюда <tex> L(G)=N(P) varepsilon</tex>-переходов, что и требовалось доказать.

==См. также = Литература =*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | Контекстно-свободные грамматики]]*[[Автоматы с магазинной памятью | Автоматы с магазинной памятью]] == Источники информации ==* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман[https://en.wikipedia. org/wiki/Pushdown_automaton#PDA_and_context-free_languages Wikipedia — PDA and context-free languages]* Введение в теорию автоматов, языков и вычислений/ Хопкрофт Д., Мотвани Р., Ульман Д. — М.:Издательский дом «Вильямс», 2002. с. 251.— ISBN 5-8459-0261-4