170
правок
Изменения
Нет описания правки
=== Построение МП-автомата по заданной КС-грамматике ===
{{Теорема|id = th1|statement = Класс контекстно-свободных языков (<tex>\mathrm{CFG}</tex>) является подмножеством класса языков, задаваемых автоматами с магазинной памятью (<tex>\mathrm{PDA}</tex>), то есть по любой КС-грамматике можно построить МП-автомат, задающий тот же язык, что и исходная грамматика.|proof = <!--
Пусть <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>.
-->
Пусть дана КС-грамматика <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>\delta</tex> задаётся следующим образом:
2) для каждого терминала <tex>a</tex> определим <tex> \delta(q, a, a) ==== Корректность построения ====\{(q, \varepsilon)\} </tex>.
<!--
Пусть <tex> w\in L(G)</tex>, тогда <tex> w </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_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>
}}
==== Пример ====
Преобразуем грамматику выражений в МП-автомат. Пусть дана грамматика:
*<tex> I \rightarrow a|b|I1|I0|Ia|Ib </tex>,
*<tex> E \rightarrow I|E*E|E+E|(E) </tex>.
Множеством входных символов является <tex> \{a,b,1,0,(,),+,*\} </tex>. Эти символы вместе с переменными <tex> I,E </tex> образуют магазинный алфавит. Функция переходов определена следующим образом:
a) <tex> \delta(q,\varepsilon,I)={(q,a), (q,b), (q,Ia), (q,Ib), (q,I0), (q,I1)};</tex>
b) <tex> \delta(q,\varepsilon,E)={(q,I), (q,E+E), (q,E*E), (q,(E))};</tex>
c) <tex> \delta(q, a, a) = \{(q, \varepsilon)\}</tex>; <tex> \delta(q, b, b) = \{(q, \varepsilon)\}</tex>; <tex> \delta(q, 0, 0) = \{(q, \varepsilon)\}</tex>; <tex> \delta(q, 1, 1) = \{(q, \varepsilon)\}</tex>.
Пункты '''a,b''' образованы по первому правилу построения функции переходов, а пункт '''c''' по второму.
=== Построение КС-грамматики по МП-автомату ===
{{Теорема
|id = th2
|statement = Класс языков, задаваемых автоматами с магазинной памятью (<tex>\mathrm{PDA}</tex>), является подмножеством класса контекстно-свободных языков (<tex>\mathrm{CFG}</tex>), то есть по любому МП-автомату можно построить КС-грамматику, задающую тот же язык, что и допускаемый автоматом..
|proof =
Наша конструкция эквивалентной грамматики использует переменные вида: <tex> [pXq]</tex> — которая означает, что в процессе изменения состояния автомата от <tex> p </tex> до <tex> q </tex>, <tex> X </tex> удалилось из стека.<br>
[[Файл:-pXq-.jpg]]
*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,...,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] \Rightarrow^* w </tex>.
*База. Пара <tex> (p,\varepsilon) </tex> должна быть в <tex> \delta(q,w,X) </tex> и <tex> w </tex> есть одиночный символ, или <tex>\varepsilon</tex>. Из построения <tex> G </tex> следует, что <tex> [qXp] \rightarrow w </tex> является продукцией, поэтому <tex> [qXp] \Rightarrow w </tex>.
*Переход. Предположим, что последовательность <tex> (q,w,X) \vdash^* (p,\varepsilon,\varepsilon)</tex> состоит из <tex> n </tex> переходов, и <tex> n>1 </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 </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>.
}}
==== Пример ====
Пусть у нас имеется <tex> P=(\{q\},\{i,e\},\{Z\},\delta,q,Z)</tex>, функция <tex> \delta </tex> задана следующим образом:
* <tex> A \rightarrow iAA | \varepsilon</tex>
В действительности можно заметить, что <tex>S</tex> и <tex>A</tex> порождают одни и те же цепочки, поэтому их можно обозначить одинаково, итого: <tex> G=(\{S\},\{i,e\},\{S \rightarrow iSS| \varepsilon\},S)</tex>
