170
правок
Изменения
Нет описания правки
=== Построение МП-автомата по заданной КС-грамматике ===
<!--
Пусть <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> задаётся следующим образом:
* для каждого правила вывода <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> w\in L(G)</tex>, тогда <tex> w </tex> имеет следующее левое порождение:
<tex> S = \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n=w</tex>.
*Переход. Предположим, что <tex> (q,w,S)\vdash^*(q,w_i,\alpha_i) </tex>. Заметим, что шаг порождения <tex> y_i \Rightarrow y_{i+1}</tex> включает замену некоторой переменной <tex> A </tex> ее продукцией <tex> \beta </tex>. Правило 1 построения МП-автомата позволяет на заменить <tex> A </tex> на вершине стека на цепочку <tex> \beta </tex>, а правило 2 позволяет затем сравнить любые терминалы на вершине со входными символами. В результате достигается МО <tex> (q,y_{i+1},\alpha_{i+1}) </tex>.
*Также заметим, что <tex> \alpha_n = \varepsilon</tex>. Таким образом <tex> (q,w,S)\vdash^*(q,\varepsilon,\varepsilon) </tex>, т.е допускает <tex> P </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> {{Утверждение---}} остаток <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>.|about** Индукционный переход: <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>. Индукционный переход доказан.|statement: Заметим, что <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> P и поочерёдно вытолкнет со стека <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> G x_2</tex>{{---}} следующая порция входа, с использованием указанной выше конструкциипрочитанная до выталкивания <tex>Y_2</tex> со стека и так далее. Формально можно заключить, то что <tex> L(Gq, x_i x_{i + 1} \ldots x_k, Y_i) \subseteq 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> {{Теорема|id = th1|statement = Класс контекстно-свободных языков (P<tex>\mathrm{CFG}</tex>) является подмножеством класса языков, задаваемых автоматами с магазинной памятью (<tex>\mathrm{PDA}</tex>).|proof= Выше доказана корректность построения МП-автомата показано, что по любой КС-грамматике. Значит множество языков КСможно построить МП-грамматик является подмножеством языковавтомат, задающий тот же язык, допускаемых МП-автоматамичто и исходная грамматика. Утверждение теоремы непосредственно следует из данного факта.
}}
<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>.
{{УтверждениеТеорема|aboutid =2th2|statement= Если КС-грамматика Класс языков, задаваемых автоматами с магазинной памятью (<tex> G \mathrm{PDA}</tex> построена по МП), является подмножеством класса контекстно-автомату свободных языков (<tex> P \mathrm{CFG}</tex>, с использованием указанной выше конструкции, то <tex> N(P) \subseteq L(G) </tex>.|proof= Выше доказана корректность построения КС-грамматики показано, что по любму МП-автомату. Значит языки допускаемые МПможно построить КС-автоматами являются подмножеством языковграмматику, задающую тот же язык, заданных КС-грамматикойчто и допускаемый автоматом. Утверждение теоремы непосредственно следует из данного факта.
}}
=== Эквивалентность языков МП-автоматов и КС-языков===
{{Теорема
|about= Об об эквивалентности языков МП-автоматов и КС-языков|statement= Множество языков, допускаемых МП-автоматами , совпадает с множеством языков, задаваемых с помощью контекстно-свободных грамматикязыков.|proof= Из утверждения 1 следует[[#th1 | Первая теорема]] гласит, что <tex> L(G) \mathrm{CFG} \subseteq N(P) \mathrm{PDA} </tex>, а [[#th2 | вторая]] {{---}} что <tex> \mathrm{PDA} \subseteq \mathrm{CFG} </tex>. Таким образом, <tex> \mathrm{PDA} = \mathrm{CFG} </tex>.}} === Замечания ==={{Утверждение|statement = Для любого МП-автомата с допуском по пустому стеку существует эквивалентный МП-автомат с одним состоянием.|proof = Построим КС-грамматику по данному автомату, затем по полученной грамматике построим МП-автомат, как указано выше. Заметим, что этот автомат будет иметь одно состояние, что и требовалось доказать.}} {{Утверждение|statement = Для любого МП-автомата с допуском по пустому стеку существует эквивалентный МП-автомат, в свою очередь из утверждения 2 следуетлюбом переходе которого на стек кладётся не больше двух символов.|proof = Построим КС-грамматику по данному автомату и приведём её к [[Нормальная форма Хомского | нормальной форме Хомского]]. Затем по полученной грамматике построим МП-автомат, как указано выше. Заметим, что в нормальной форме Хомского правые части всех правил имеют длину не больше двух, поэтому в любом переходе в полученном автомате на стек кладётся не больше двух символов.}} {{Утверждение|statement = Для любого МП-автомата с допуском по пустому стеку существует эквивалентный МП-автомат без <tex> N(P) \subseteq L(G) varepsilon</tex>-переходов. Отсюда |proof = Построим КС-грамматику по данному автомату, затем по полученной грамматике построим МП-автомат, как указано выше. Заметим, что этот автомат не будет иметь <tex> L(G)=N(P) \varepsilon</tex>-переходов, что и требовалось доказать.
}}
=== Литература ===
* Джон ''ХопкрофтД., Раджив МотваниР., Джеффри УльманД. '' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.:Издательский дом «Вильямс», 2002. {{---}} С. 251.
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
