170
правок
Изменения
Нет описания правки
: Заметим, что <tex>\alpha_n = \varepsilon, v_n = w, x_n = \varepsilon</tex>, поэтому <tex>(q, w, S) \vdash^* (q, \varepsilon, \varepsilon)</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>N \Rightarrow^* x</tex>.
** База (1 переход): <br> Если <tex>(q, x, N) \vdash^* (q, \varepsilon, \varepsilon)</tex>, то <tex>x = \varepsilon</tex> и в грамматике присутствует правило <tex>N \rightarrow \varepsilon</tex>, по которому выводится <tex>\varepsilon = x</tex>.
** Индукционный переход: <br> Предположим, что автомат <tex>A</tex> совершает <tex>n</tex> шагов (<tex>n > 1</tex>). Изначально на вершине стеке находится <tex>S</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> и <texY_itex>Y_i</tex>. Значит, <tex>Y_i \Rightarrow^* x_i</tex> за 0 шагов. <br> Таким образом, получаем, что <tex>N \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>N</tex>, получаем, что <tex>S \Rightarrow^* w</tex>
}}
{{Теорема
|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> построим следующим образом:
1) для каждого состояния <tex>p \in Q</tex> добавим правило <tex>S \rightarrow [q_0 z_0 p]</tex>;
2) для каждого перехода <tex>\delta(p, a, X) = \{(r, \gamma_1 \gamma_2 \ldots \gamma_k)\}</tex> сделаем следующее: для всех упорядоченных списков состояний <tex>\{z_1, z_2 \ldots z_k\} \in Q^k</tex> добавим правило <tex>[p X z_k] \rightarrow a [r \gamma_1 z_1] [z_1 \gamma_2 z_2] \ldots [z_{k - 1} \gamma_k z_k]</tex>, если <tex>k > 0</tex>, и <tex>[p X r] \rightarrow a</tex>, если <tex>k = 0</tex>.
Докажем корректность неформального описания нетерминалов <tex>[pXq]</tex>, то есть что <tex>[pXq] \Rightarrow^* w \iff (p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</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, 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, \gamma_1 \gamma_2 \ldots \gamma_k)\} \in \delta(p, a, X)</tex>. По построению в грамматике должно присутствовать правило <tex>[p X z_k] \rightarrow a [r\gamma_1 z_1] [z_1 \gamma_2 z_2] \ldots [z_{k - 1} \gamma_k z_k]</tex> для любой последовательности состояний <tex>\{z_i\}</tex>. Пусть <tex>x = w_1 w_2 \ldots w_k</tex>, где <tex>w_i</tex> {{---}} входная цепочка, которая прочитывается до удаления <tex>\gamma_i</tex> со стека, то есть найдётся такая последовательность состояний <tex>\{z_i\}</tex>, что <tex>(z_{i - 1}, w_i, \gamma_i) \vdash^* (z_i, \varepsilon, \varepsilon)</tex>, причём заканчивается всё в <tex>q = z_k</tex>. Заметим, что все эти выводы содержат менее <tex>n</tex> переходов, а значит, по индукционному предположению <tex>[z_{i - 1} \gamma_i z_i] \Rightarrow^* w_i</tex> для всех <tex>i</tex>. <br> Собирая вышесказанное, получаем <tex>[p X z_k] \Rightarrow a [r\gamma_1 z_1] [z_1 \gamma_2 z_2] \ldots [z_{k - 1} \gamma_k z_k] \Rightarrow^* a w_1 w_2 \ldots w_k = w</tex>. Так как <tex>z_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>\delta(p, w, X) = \{(q, \varepsilon)\}</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 z_k] \Rightarrow a [r \gamma_1 z_1] [z_1 \gamma_2 z_2] \ldots [z_{k - 1} \gamma_k z_k] \Rightarrow^* w</tex>, где <tex>z_k = q</tex> и <tex>(r, \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>[z_{i - 1} \gamma_i z_i] \Rightarrow^* w_i</tex>. Так как все эти выводы содержат менее <tex>n</tex> шагов, то по индукционному предположению для всех <tex>i</tex> выполнено <tex>(z_{i - 1}, w_i, \gamma_i) \vdash^* (z_i, \varepsilon, \varepsilon)</tex>. Собирая всё вместе, получаем <tex>(r, w_1 w_2 \ldots w_k, \gamma_1 \gamma_2 \ldots \gamma_k) \vdash^* (z_1, w_2 w_3 \ldots w_k, \gamma_2 \gamma_3 \ldots \gamma_k) \vdash^* \ldots \vdash^* (z_k, \varepsilon, \varepsilon)</tex>. Так как <tex>(r, \gamma_1 \gamma_2 \ldots \gamma_k) \in \delta(p, a, X)</tex> и <tex>z_k = q</tex>, то в итоге <tex>(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>.
Таким образом, мы доказали, что <tex>[pXq] \Rightarrow^* w \iff (p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>. Заметим, что <tex>S \Rightarrow^* w</tex> тогда и только тогда, когда найдётся <tex>p</tex>, что <tex>[q_0 z_0 p] \Rightarrow^* w</tex>. По доказаному выше это равносильно тому, что <tex>(q0, w, z0) \vdash^* (p, \varepsilon, \varepsilon)</tex>, то есть что <tex>A</tex> допускает <tex>w</tex> по пустому стеку. Суммируя всё вышесказанное, получаем, что построенная грамматика <tex>\Gamma</tex> порождает слово <tex>w</tex> тогда и только тогда, когда оно допускается автоматом <tex>A</tex>.
<!--
Наша конструкция эквивалентной грамматики использует переменные вида: <tex> [pXq]</tex> — которая означает, что в процессе изменения состояния автомата от <tex> p </tex> до <tex> q </tex>, <tex> X </tex> удалилось из стека.<br>
[[Файл:-pXq-.jpg]]
<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 </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_i</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>.
-->
}}
