Изменения

# * для каждого правила вывода <tex>V \rightarrow \gamma \in P</tex> определим <tex>\delta(q, \varepsilon, V) = \{(q, \gamma)\}</tex>;# * для каждого терминала <tex>a</tex> определим <tex> \delta(q, a, a) = \{(q, \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> {{---}} остаток <tex>\gamma_i</tex>, то есть <tex>\gamma_i = v_i\alpha_i</tex>, причём <tex>v_i \in \Sigma^*</tex>, а <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>, можно оставить на стеке <tex>\alpha_i</tex>.*:* База (<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^* (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, V) = \{(q, \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, x_i, \alpha_i) \vdash^* (q, x_{i + 1}, \alpha_{i + 1})</tex>, а значит, <tex>(q, w, S) \vdash^* (q, x_{i + 1}, \alpha_{i + 1})</tex>. Индукционный переход доказан.

* ;Пусть <tex>(q, w, S) \vdash^* (q, \varepsilon, \varepsilon)</tex>. : Воспользуемся индукцией по числу переходов в автомате и докажем для любой строки <tex>x</tex> и нетерминала <tex>M \in N</tex>, что если <tex>(q, x, M) \vdash^* (q, \varepsilon, \varepsilon)</tex>, то <tex>M \Rightarrow^* x</tex>.*:* База (1 переход): <br> Если <tex>(q, x, M) \vdash^* (q, \varepsilon, \varepsilon)</tex>, то <tex>x = \varepsilon</tex> и в грамматике присутствует правило <tex>M \rightarrow \varepsilon</tex>, по которому выводится <tex>\varepsilon = x</tex>.*:* Индукционный переход: <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^* (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^* w.</tex>

Преобразуем Поскольку доказательство теоремы конструктивно, то используя правила перехода, описанные в ней, можно преобразовать любую КС-грамматику в МП-автомат. Рассмотрим грамматику слов над алфавитом <tex>\{0, 1\}</tex>, в которых поровну одинаковое количество нулей и единиц, в МП-автомат. Пусть дана грамматика:* : <tex> S \rightarrow 0S1 </tex>;* : <tex> S \rightarrow 1S0 </tex>;* : <tex> S \rightarrow \varepsilon </tex>.

* : <tex>\delta(q, \varepsilon, S) = \{(q, 0S1), (q, 1S0), (q, \varepsilon)\}</tex> (в соответствии с первым пунктом построения <tex>\delta</tex>);

* : <tex> \delta(q, 0, 0)= \{(q, \varepsilon)\}</tex>; <tex> \delta(q, 1, 1)= \{(q, \varepsilon)\}</tex> (в соответствии со вторым пунктом построения <tex>\delta</tex>).

Пусть дан МП-автомат с допуском по пустому стеку <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 \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>(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>. : Докажем, что <tex>[pXq] \Rightarrow^* w</tex>, используя индукцию по числу переходов в автомате.*:* База (1 переход): <br> Раз выполняется только один переход, то длина <tex>w</tex> не больше единицы и <tex>(q, \varepsilon) \in \delta(p, 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>w = ax</tex> (<tex>a</tex> {{---}} символ из <tex>\Sigma</tex> или <tex>\varepsilon</tex>). Значит, <tex>(r_0, \gamma_1 \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, \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 \ldots w_k = w</tex>. Так как <tex>r_k = q</tex>, то <tex>[pXq] \Rightarrow^* w</tex>, тем самым индукционный переход доказан.* Пусть <tex>[pXq] \Rightarrow^* w</tex>. Докажем, что <tex>(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>, используя индукцию по числу шагов в порождении.** База (1 шаг): <br> Если <tex>[pXq] \Rightarrow^* w</tex> за один шаг, то в <tex>\Gamma</tex> должно быть правило вывода <tex>[pXq] \rightarrow w</tex>, а значит, в автомате должен быть переход <tex>(q, \varepsilon) \in \delta(p, w, X)</tex> и <tex>w</tex> не может иметь длину больше единицы. Таким образом, <tex>(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>.** Индукционный переход: <br> Предположим, что <tex>[pXq] \Rightarrow^* w </tex> за <tex>n > 1</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] \Rightarrow^* w</tex>, где <tex>r_k = q</tex> и <tex>(r_0, \gamma_1 \gamma_2 \ldots \gamma_k) \in \delta(p, a, X)</tex>. Вновь представим <tex>w</tex> в виде <tex>w = a w_1 w_2 \ldots w_k</tex> так, что <tex>[r_{i - 1} \gamma_i r_i] \Rightarrow^* w_i</tex>. Так как все эти выводы содержат менее <tex>n</tex> шагов, то по индукционному предположению для всех <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 \delta(p, a, X)</tex> и <tex>r_k = q</tex>, то в итоге <tex>(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>.

Таким образом, мы доказали, что ;Пусть <tex>[pXq] \Rightarrow^* w \iff </tex>.: Докажем, что <tex>(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>, используя индукцию по числу шагов в порождении. Заметим, что :*База (1 шаг): <br> Если <tex>S [pXq] \Rightarrow^* w</tex> тогда и только тогдаза один шаг, когда найдётся то в <tex>p\Gamma</tex>, что должно быть правило вывода <tex>[q_0 z_0 ppXq] \Rightarrow^* rightarrow w</tex>, а значит, в автомате должен быть переход <tex>(q, \varepsilon) \in \delta(p, w, X)</tex> и <tex>w</tex>не может иметь длину больше единицы. По доказаному выше это равносильно томуТаким образом, что <tex>(q_0p, w, z_0X) \vdash^* (pq, \varepsilon, \varepsilon)</tex>.:*Индукционный переход: <br> Предположим, то есть что <tex>A[pXq] \Rightarrow^* w </tex> за <tex>n > 1</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] \Rightarrow^* w</tex>, где <tex>r_k = q</tex> и <tex>(r_0, \gamma_1 \gamma_2 \ldots \gamma_k) \in \delta(p, a, X)</tex>. Вновь представим <tex>w</tex> допускает в виде <tex>w= a w_1 w_2 \ldots w_k</tex> так, что <tex>[r_{i - 1} \gamma_i r_i] \Rightarrow^* w_i</tex>. Так как все эти выводы содержат менее <tex>n</tex> шагов, то по пустому стекуиндукционному предположению для всех <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) \Gammain \delta(p, a, X)</tex> порождает слово и <tex>wr_k = q</tex> тогда и только тогда, когда оно допускается автоматом то в итоге <tex>A(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>.

<!--Наша конструкция эквивалентной грамматики использует переменные вида: <tex> [pXq]</tex> — которая означаетТаким образом, что в процессе изменения состояния автомата от <tex> p </tex> до <tex> q </tex>, <tex> X </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> имеет следующие продукции:Rightarrow^*a) продукции <tex> S w \rightarrow [q_0Z_0p] </tex> для всех <tex> iff (p </tex>, таким образом <tex> (q,w,Z_0X)\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,...,r_k</tex> в грамматике <tex> G </tex> есть продукция <tex> [qXr_k]\rightarrow a[r Y_1 r_1][r_1 Y_1 r_2]...[r_{k-1} Y_k r_k]</tex>.ДокажемЗаметим, что если <tex> (q,w,X) \vdash^* (p,\varepsilon,\varepsilon)</tex>, то <tex> [qXp] S \Rightarrow^* w </tex>.*База. Пара <tex> (p,\varepsilon) </tex> должна быть в <tex> \delta(q,w,X) </tex> тогда и <tex> w </tex> есть одиночный символтолько тогда, или когда найдётся <tex>\varepsilonp</tex>. Из построения <tex> G </tex> следует, что <tex> [qXp] \rightarrow w </tex> является продукцией, поэтому <tex> [qXpq_0 z_0 p] \Rightarrow ^* w </tex>.*Переход. ПредположимПо доказанному выше это равносильно тому, что последовательность <tex> (qq_0,w,Xz_0) \vdash^* (p,\varepsilon,\varepsilon)</tex> состоит из <tex> n </tex> переходов, и то есть что <tex> n>1 A</tex>. Первый переход должен иметь вид:допускает <tex> (q,w,Z) \vdash (r_0,X,Y_1Y_2...Y_k) \vdash^* (p,\varepsilon,\varepsilon) </tex>по пустому стеку. Суммируя всё вышесказанное, где <tex> w=aX </tex> для некоторого <tex> a </tex>получаем, которое является либо символом из что построенная грамматика <tex> \Gamma </tex>, либо порождает слово <tex> \varepsilon w</tex>. По построению <tex> G </tex> существует продукция <tex> [qXr_k] \rightarrow a[r_0 Y_1 r_1][r_1 Y_2 r_2]...[r_{k-1} Y_k r_k] </tex>, где <tex> r_i</tex> — состояния из <tex> Q </tex>, тогда и <tex> r_k = p </tex>. Пусть <tex> X=w_1 w_2 ... w_k </tex>, где <tex> w_i </tex> — входная цепочка, которая прочитывается до удаления <tex> Y_i </tex> из стека, только тогда <tex> (r_{i-1},w_i, Y_i) \vdash^* (r_i, \varepsilon, \varepsilon)</tex>. По скольку ни одна из этих последовательностей переходов не содержит более, чем <tex> n </tex> переходов, к ним можно применить предположение индукции когда оно допускается автоматом <tex> [r_{i-1}Y_ir_i] \Rightarrow^* w_iA</tex>. Соберем эти порождения вместе: <br><tex> [qXr_k] \Rightarrow a[r_0Y_1r_1][r_1Y_1r_2]...[r_{k-1}Y_kr_k] \Rightarrow^* aw_1[r_1Y_1r_2]...[r_{k-1}Y_kr_k] \Rightarrow^* aw_1w_2[r_2Y_3r_3]...[r_{k-1}Y_kr_k] \Rightarrow^*... \Rightarrow^* aw_1w_2...w_k = w</tex>.-->

;Википедия*[[Формальные грамматики | Формальные грамматики]https://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_context-free_languages Wikipedia — PDA and context-free languages];Другие викиконспекты*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | Контекстно-свободные грамматики]] *[[Автоматы с магазинной памятью | Автоматы с магазинной памятью]] [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность | МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]

* ''Введение в теорию автоматов, языков и вычислений / Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} — М.:Издательский дом «Вильямс», 2002. {{с. 251. — ISBN 5-8459-0261-}} С. 251.4