Совпадение множества языков МП-автоматов и контекстно-свободных языков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
=== Построение МП-автомата по заданной КС-грамматике ===
+
== Построение МП-автомата по заданной КС-грамматике ==
  
 
{{Теорема
 
{{Теорема
 
|id = th1
 
|id = th1
|statement = Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | контекстно-свободных языков]] (<tex>\mathrm{CFG}</tex>) является подмножеством класса языков, задаваемых [[Автоматы с магазинной памятью | автоматами с магазинной памятью]] (<tex>\mathrm{PDA}</tex>), то есть по любой КС-грамматике можно построить МП-автомат, задающий тот же язык, что и исходная грамматика.
+
|statement = Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | контекстно-свободных языков]] <tex>(\mathrm{CFG})</tex> является подмножеством класса языков, задаваемых [[Автоматы с магазинной памятью | автоматами с магазинной памятью]] <tex>(\mathrm{PDA})</tex>, то есть по любой КС-грамматике можно построить МП-автомат, задающий тот же язык, что и исходная грамматика.
 
|proof =  
 
|proof =  
 
Пусть дана КС-грамматика <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex>. Поскольку классы языков, допускаемых МП-автоматами по допускающему состоянию и по пустому стеку, [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность | совпадают]], достаточно построить автомат с допуском по пустому стеку.
 
Пусть дана КС-грамматика <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex>. Поскольку классы языков, допускаемых МП-автоматами по допускающему состоянию и по пустому стеку, [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность | совпадают]], достаточно построить автомат с допуском по пустому стеку.
Строка 11: Строка 11:
 
[[Файл:Delta.png | thumb | right | Добавим такие переходы для каждого терминала <tex>a</tex> и правила вывода <tex>V \rightarrow \gamma</tex>]]
 
[[Файл:Delta.png | thumb | right | Добавим такие переходы для каждого терминала <tex>a</tex> и правила вывода <tex>V \rightarrow \gamma</tex>]]
  
# для каждого правила вывода <tex>V \rightarrow \gamma \in P</tex> определим <tex>\delta(q, \varepsilon, V) = \{(q, \gamma)\}</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>a</tex> определим <tex> \delta(q, a, a) = \{(q, \varepsilon)\} </tex>.
  
 
Покажем, что язык, допускаемый автоматом <tex>A</tex>, совпадает с языком грамматики <tex>\Gamma</tex>, то есть что <tex>S \Rightarrow^* w \iff (q, w, S) \vdash^* (q, \varepsilon, \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> {{---}} остаток <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>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>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>. Индукционный переход доказан.
+
:* '''Индукционный переход:''' <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>\alpha_n = \varepsilon, v_n = w, x_n = \varepsilon</tex>, поэтому <tex>(q, w, S) \vdash^* (q, \varepsilon, \varepsilon)</tex>.
 
: Заметим, что <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>M \Rightarrow^* x</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> Пусть в автомате один переход. <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>.
+
:* '''Индукционный переход:''' <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>w</tex> вместо <tex>x</tex> и <tex>S</tex> вместо <tex>M</tex>, получаем, что <tex>S \Rightarrow^* w.
 +
</tex>
 
}}
 
}}
  
==== Пример ====
+
=== Пример ===
Преобразуем КС-грамматику слов над алфавитом <tex>\{0, 1\}</tex>, в которых поровну нулей и единиц, в МП-автомат. Пусть дана грамматика:
+
Поскольку доказательство теоремы конструктивно, то используя правила перехода, описанные в ней, можно преобразовать любую КС-грамматику в МП-автомат. Рассмотрим грамматику слов над алфавитом <tex>\{0, 1\}</tex>, в которых одинаковое количество нулей и единиц:
* <tex> S \rightarrow 0S1 </tex>;
+
: <tex> S \rightarrow 0S1 </tex>
* <tex> S \rightarrow 1S0 </tex>;
+
: <tex> S \rightarrow 1S0 </tex>
* <tex> S \rightarrow \varepsilon </tex>.
+
: <tex> S \rightarrow \varepsilon </tex>
 
Множеством терминалов является <tex>\Sigma = \{0, 1\}</tex>, а нетерминалов {{---}} <tex>N = \{S\}</tex>. Таким образом, стековый алфавит состоит из <tex>0, 1, S</tex>. Функция переходов <tex>\delta</tex> определена следующим образом:
 
Множеством терминалов является <tex>\Sigma = \{0, 1\}</tex>, а нетерминалов {{---}} <tex>N = \{S\}</tex>. Таким образом, стековый алфавит состоит из <tex>0, 1, S</tex>. Функция переходов <tex>\delta</tex> определена следующим образом:
  
* <tex>\delta(q, \varepsilon, S) = \{(q, 0S1), (q, 1S0), (q, \varepsilon)\}</tex> (в соответствии с первым пунктом построения <tex>\delta</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> \delta(q, 0, 0)= \{(q, \varepsilon)\}</tex>; <tex> \delta(q, 1, 1)= \{(q, \varepsilon)\}</tex> (в соответствии со вторым пунктом построения <tex>\delta</tex>)
  
 
Получившийся автомат:
 
Получившийся автомат:
 +
 
[[Файл:Example1.png]]
 
[[Файл:Example1.png]]
  
=== Построение КС-грамматики по МП-автомату ===
+
== Построение КС-грамматики по МП-автомату ==
 
{{Теорема
 
{{Теорема
 
|id = th2
 
|id = th2
|statement = Класс языков, задаваемых автоматами с магазинной памятью (<tex>\mathrm{PDA}</tex>), является подмножеством класса контекстно-свободных языков (<tex>\mathrm{CFG}</tex>), то есть по любому МП-автомату можно построить КС-грамматику, задающую тот же язык, что и допускаемый автоматом.
+
|statement = Класс языков, задаваемых автоматами с магазинной памятью <tex>(\mathrm{PDA})</tex>, является подмножеством класса контекстно-свободных языков <tex>(\mathrm{CFG})</tex>, то есть по любому МП-автомату можно построить КС-грамматику, задающую тот же язык, что и допускаемый автоматом.
 
|proof =  
 
|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>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</tex> построим следующим образом:
  
# для каждого состояния <tex>p \in Q</tex> добавим правило <tex>S \rightarrow [q_0 z_0 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>(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, X)</tex> в <tex>(q, \varepsilon)</tex>. Формально это можно записать следующим образом: <tex>[pXq] \Rightarrow^* w \iff (p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>. Докажем это утверждение:
 
Нетерминал <tex>[pXq]</tex> должен выводить только те строки <tex>w</tex>, которые переводят автомат из состояния <tex>(p, X)</tex> в <tex>(q, \varepsilon)</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>, используя индукцию по числу переходов в автомате.
+
;Пусть <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> Пусть выполняется только один переход.<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>, тем самым индукционный переход доказан.
+
:*'''Индукционный переход:'''<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 (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>(q_0, w, z_0) \vdash^* (p, \varepsilon, \varepsilon)</tex>, то есть что <tex>A</tex> допускает <tex>w</tex> по пустому стеку. Суммируя всё вышесказанное, получаем, что построенная грамматика <tex>\Gamma</tex> порождает слово <tex>w</tex> тогда и только тогда, когда оно допускается автоматом <tex>A</tex>.
+
;Пусть <tex>[pXq] \Rightarrow^* w</tex>.: Докажем, что <tex>(p, w, X) \vdash^* (q, \varepsilon, \varepsilon)</tex>, используя индукцию по числу шагов в порождении.
 +
:*'''База:''' <br> Пусть <tex>[pXq] \Rightarrow^* w</tex> за один шаг.<br> Тогда в <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 (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>(q_0, w, z_0) \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> 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,...,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>A = \langle \{i,e\}, \{Z\}, \{q\}, q, Z, \delta \rangle</tex>, функция <tex>\delta</tex> задана следующим образом:
 
Пусть у нас имеется МП-автомат <tex>A = \langle \{i,e\}, \{Z\}, \{q\}, q, Z, \delta \rangle</tex>, функция <tex>\delta</tex> задана следующим образом:
*<tex>\delta(q, i, Z) = \{(q, ZZ)\}</tex>,
+
:<tex>\delta(q, i, Z) = \{(q, ZZ)\}</tex>
*<tex>\delta(q, e, Z) = \{(q, \varepsilon)\}</tex>.
+
:<tex>\delta(q, e, Z) = \{(q, \varepsilon)\}</tex>
  
 
[[Файл:Example2.png]]
 
[[Файл:Example2.png]]
Строка 92: Строка 78:
 
Так как стековый алфавит <tex>A</tex> содержит лишь один символ и одно состояние, то в построенной грамматике будет лишь 2 нетерминала:
 
Так как стековый алфавит <tex>A</tex> содержит лишь один символ и одно состояние, то в построенной грамматике будет лишь 2 нетерминала:
  
* <tex>S</tex> — стартовый нетерминал.
+
*<tex>S</tex> — стартовый нетерминал.
  
* <tex>[qZq]</tex> — единственная тройка, которую можно собрать из состояний автомата и символов стекового алфавита.
+
*<tex>[qZq]</tex> — единственная тройка, которую можно собрать из состояний автомата и символов стекового алфавита.
  
 
Также грамматика имеет следующие правила вывода:
 
Также грамматика имеет следующие правила вывода:
Строка 101: Строка 87:
 
* Из <tex>\delta(q,e,Z)=\{(q,\varepsilon)\}</tex> получаем правило вывода <tex>[qZq] \rightarrow e</tex>
 
* Из <tex>\delta(q,e,Z)=\{(q,\varepsilon)\}</tex> получаем правило вывода <tex>[qZq] \rightarrow e</tex>
 
Для удобства тройку <tex>[qZq]</tex> можно заменить символом <tex>A</tex>, в таком случае правила вывода в грамматике будут следующие:
 
Для удобства тройку <tex>[qZq]</tex> можно заменить символом <tex>A</tex>, в таком случае правила вывода в грамматике будут следующие:
* <tex>S \rightarrow A</tex>;
+
:<tex>S \rightarrow A</tex>
* <tex>A \rightarrow iAA</tex>;
+
:<tex>A \rightarrow iAA</tex>
* <tex>A \rightarrow e</tex>.
+
:<tex>A \rightarrow e</tex>
 
Упростим грамматику, заменив <tex>A</tex> на <tex>S</tex> (очевидно, она не поменяется), и получим в результате <tex>\Gamma = \langle\{i,e\}, \{S\}, S, \{S \rightarrow iSS | e\}\rangle</tex>
 
Упростим грамматику, заменив <tex>A</tex> на <tex>S</tex> (очевидно, она не поменяется), и получим в результате <tex>\Gamma = \langle\{i,e\}, \{S\}, S, \{S \rightarrow iSS | e\}\rangle</tex>
  
=== Эквивалентность языков МП-автоматов и КС-языков===
+
== Эквивалентность языков МП-автоматов и КС-языков==
 
{{Теорема
 
{{Теорема
 
|about = об эквивалентности языков МП-автоматов и КС-языков
 
|about = об эквивалентности языков МП-автоматов и КС-языков
Строка 113: Строка 99:
 
}}
 
}}
  
=== Следствия ===
+
== Следствия ==
 
{{Утверждение
 
{{Утверждение
 
|statement = Для любого МП-автомата с допуском по пустому стеку существует эквивалентный МП-автомат с одним состоянием.
 
|statement = Для любого МП-автомата с допуском по пустому стеку существует эквивалентный МП-автомат с одним состоянием.
Строка 128: Строка 114:
 
|proof = Построим КС-грамматику по данному автомату, затем по полученной грамматике построим МП-автомат, как указано выше. Заметим, что этот автомат не будет иметь <tex>\varepsilon</tex>-переходов, что и требовалось доказать.
 
|proof = Построим КС-грамматику по данному автомату, затем по полученной грамматике построим МП-автомат, как указано выше. Заметим, что этот автомат не будет иметь <tex>\varepsilon</tex>-переходов, что и требовалось доказать.
 
}}
 
}}
=== Ссылки ===
+
== См. также ==
[[Формальные грамматики | Формальные грамматики]]
+
*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | Контекстно-свободные грамматики]]
 
+
*[[Автоматы с магазинной памятью | Автоматы с магазинной памятью]]
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | Контекстно-свободные грамматики]]
 
 
 
[[Автоматы с магазинной памятью | Автоматы с магазинной памятью]]
 
 
 
[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность | МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
 
  
=== Литература ===
+
== Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.:Издательский дом «Вильямс», 2002. {{---}} С. 251.
+
*[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
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: МП-автоматы]]

Текущая версия на 22:10, 15 марта 2016

Построение МП-автомата по заданной КС-грамматике[править]

Теорема:
Класс контекстно-свободных языков [math](\mathrm{CFG})[/math] является подмножеством класса языков, задаваемых автоматами с магазинной памятью [math](\mathrm{PDA})[/math], то есть по любой КС-грамматике можно построить МП-автомат, задающий тот же язык, что и исходная грамматика.
Доказательство:
[math]\triangleright[/math]

Пусть дана КС-грамматика [math]\Gamma =\langle \Sigma, N, S, P\rangle[/math]. Поскольку классы языков, допускаемых МП-автоматами по допускающему состоянию и по пустому стеку, совпадают, достаточно построить автомат с допуском по пустому стеку.

Построим автомат из одного состояния [math]q[/math] с входным алфавитом [math]\Sigma[/math], стековым алфавитом [math]N \cup \Sigma[/math], маркером дна [math]S[/math] и функцией перехода [math]\delta[/math], определённой ниже. Формально [math]A = \langle \Sigma, N \cup \Sigma, \{q\}, q, S, \delta \rangle[/math], где [math]\delta[/math] задаётся следующим образом:

Добавим такие переходы для каждого терминала [math]a[/math] и правила вывода [math]V \rightarrow \gamma[/math]
  • для каждого правила вывода [math]V \rightarrow \gamma \in P[/math] определим [math]\delta(q, \varepsilon, V) = \{(q, \gamma)\}[/math];
  • для каждого терминала [math]a[/math] определим [math] \delta(q, a, a) = \{(q, \varepsilon)\} [/math].

Покажем, что язык, допускаемый автоматом [math]A[/math], совпадает с языком грамматики [math]\Gamma[/math], то есть что [math]S \Rightarrow^* w \iff (q, w, S) \vdash^* (q, \varepsilon, \varepsilon)[/math]:

Пусть [math]S \Rightarrow^* w[/math].
Рассмотрим левосторонний вывод [math]S = \gamma_0 \Rightarrow \gamma_1 \Rightarrow ... \Rightarrow \gamma_n=w[/math]. Обозначим как [math]v_i[/math] наибольший префикс [math]\gamma_i[/math], состоящий только из терминалов, а [math]\alpha_i[/math] — остаток [math]\gamma_i[/math], то есть [math]\gamma_i = v_i\alpha_i[/math], причём [math]v_i \in \Sigma^*[/math], а [math]\alpha_i[/math] начинается с нетерминала (либо пустая). С помощью индукции по [math]i[/math] докажем, что [math](q, w, S) \vdash^* (q, x_i, \alpha_i)[/math] для [math]i \leq n[/math], где [math]x_i[/math] — то, что остаётся после чтения [math]v_i[/math], то есть [math]v_ix_i = w[/math]. Иными словами, переходя по автомату по символам [math]v_i[/math], можно оставить на стеке [math]\alpha_i[/math].
  • База:
    Пусть [math]i = 0[/math].
    В этом случае [math]\gamma_0 = S[/math], поэтому [math]v_0 = \varepsilon, \alpha_0 = S, x_i = w[/math]. Очевидно, [math](q, w, S) \vdash^* (q, w, S)[/math].
  • Индукционный переход:
    Пусть [math](q, w, S) \vdash^* (q, x_i, \alpha_i)[/math] для [math]i \lt n[/math]. [math]\alpha_i[/math] по определению начинается с какого-то нетерминала [math]V[/math] (если [math]\alpha_i = \varepsilon[/math], то получена [math]\gamma_n[/math], а мы предположили, что [math]i \lt n[/math]), то есть [math]\alpha_i = Vq_i[/math] Поскольку мы рассматриваем левосторонний вывод, то переход [math]\gamma_i \Rightarrow \gamma_{i + 1}[/math] включает замену нетерминала [math]V[/math] на какую-то цепочку [math]\beta[/math] по правилу [math]V \rightarrow \beta[/math]. Так как [math]\gamma_i = v_i \alpha_i = v_i V q_i[/math], то [math]\gamma_{i + 1} = v_i \beta q_i = v_{i + 1} \alpha_{i + 1}[/math]. В автомате [math]A[/math] по построению присутствует правило перехода [math]\delta(q, \varepsilon, V) = \{(q, \beta)\}[/math], поэтому [math]\alpha_i[/math] на стеке можно заменить на [math]\beta q_i[/math]. Заметим, что [math]\beta q_i[/math] представляет собой конкатенацию нескольких терминалов из [math]w[/math] и [math]\alpha_{i + 1}[/math]. Считывая очередные символы строки [math]w[/math], будем переходить по автомату, убирая терминалы со стека, пока не встретим нетерминал. Таким образом, на стеке окажется [math]\alpha_{i+1}[/math]. Получили, что [math](q, x_i, \alpha_i) \vdash^* (q, x_{i + 1}, \alpha_{i + 1})[/math], а значит, [math](q, w, S) \vdash^* (q, x_{i + 1}, \alpha_{i + 1})[/math]. Индукционный переход доказан.
Заметим, что [math]\alpha_n = \varepsilon, v_n = w, x_n = \varepsilon[/math], поэтому [math](q, w, S) \vdash^* (q, \varepsilon, \varepsilon)[/math].
Пусть [math](q, w, S) \vdash^* (q, \varepsilon, \varepsilon)[/math].
Воспользуемся индукцией по числу переходов в автомате и докажем для любой строки [math]x[/math] и нетерминала [math]M \in N[/math], что если [math](q, x, M) \vdash^* (q, \varepsilon, \varepsilon)[/math], то [math]M \Rightarrow^* x[/math].
  • База:
    Пусть в автомате один переход.
    Если [math](q, x, M) \vdash^* (q, \varepsilon, \varepsilon)[/math], то [math]x = \varepsilon[/math] и в грамматике присутствует правило [math]M \rightarrow \varepsilon[/math], по которому выводится [math]\varepsilon = x[/math].
  • Индукционный переход:
    Предположим, что автомат [math]A[/math] совершает [math]n[/math] шагов ([math]n \gt 1[/math]). Изначально на вершине стеке находится [math]M[/math], поэтому первый переход совершается по какому-то правилу из первого пункта построения [math]\delta[/math], и на стеке оказывается последовательность из терминалов и нетерминалов [math]Y_1 Y_2 \ldots Y_k[/math]. В процессе следующих [math]n - 1[/math] переходов автомат прочитает строку [math]x[/math] и поочерёдно вытолкнет со стека [math]Y_1 Y_2 \ldots Y_k[/math]. Разобьём [math]w[/math] на подстроки [math]x_1 x_2 \ldots x_k[/math], где [math]x_1[/math] — порция входа, прочитанная до выталкивания [math]Y_1[/math] со стека, [math]x_2[/math] — следующая порция входа, прочитанная до выталкивания [math]Y_2[/math] со стека и так далее. Формально можно заключить, что [math](q, x_i x_{i + 1} \ldots x_k, Y_i) \vdash^* (q, x_{i + 1} \ldots x_k, \varepsilon)[/math], причём менее чем за [math]n[/math] шагов. Если [math]Y_i[/math] — нетерминал, то по индукционному предположению имеем, что [math]Y_i \Rightarrow^* x_i[/math]. Если же [math]Y_i[/math] — терминал, то должен совершаться только один переход, в котором проверяется совпадение [math]x_i[/math] и [math]Y_i[/math]. Значит, [math]Y_i \Rightarrow^* x_i[/math] за 0 шагов.
    Таким образом, получаем, что [math]M \Rightarrow Y_1 Y_2 \ldots Y_k \Rightarrow^* x_1 x_2 \ldots x_k = x[/math].
Подставляя [math]w[/math] вместо [math]x[/math] и [math]S[/math] вместо [math]M[/math], получаем, что [math]S \Rightarrow^* w. [/math]
[math]\triangleleft[/math]

Пример[править]

Поскольку доказательство теоремы конструктивно, то используя правила перехода, описанные в ней, можно преобразовать любую КС-грамматику в МП-автомат. Рассмотрим грамматику слов над алфавитом [math]\{0, 1\}[/math], в которых одинаковое количество нулей и единиц:

[math] S \rightarrow 0S1 [/math]
[math] S \rightarrow 1S0 [/math]
[math] S \rightarrow \varepsilon [/math]

Множеством терминалов является [math]\Sigma = \{0, 1\}[/math], а нетерминалов — [math]N = \{S\}[/math]. Таким образом, стековый алфавит состоит из [math]0, 1, S[/math]. Функция переходов [math]\delta[/math] определена следующим образом:

[math]\delta(q, \varepsilon, S) = \{(q, 0S1), (q, 1S0), (q, \varepsilon)\}[/math] (в соответствии с первым пунктом построения [math]\delta[/math])
[math] \delta(q, 0, 0)= \{(q, \varepsilon)\}[/math]; [math] \delta(q, 1, 1)= \{(q, \varepsilon)\}[/math] (в соответствии со вторым пунктом построения [math]\delta[/math])

Получившийся автомат:

Example1.png

Построение КС-грамматики по МП-автомату[править]

Теорема:
Класс языков, задаваемых автоматами с магазинной памятью [math](\mathrm{PDA})[/math], является подмножеством класса контекстно-свободных языков [math](\mathrm{CFG})[/math], то есть по любому МП-автомату можно построить КС-грамматику, задающую тот же язык, что и допускаемый автоматом.
Доказательство:
[math]\triangleright[/math]

Пусть дан МП-автомат с допуском по пустому стеку [math]A = \langle \Sigma, \Pi, Q, q_0 \in Q, z_0, \delta \rangle[/math]. Как отмечалось ранее, предположение о допуске по пустому стеку не умаляет общности. Построим эквивалентную ему КС-грамматику [math]\Gamma = \langle \Sigma, N, S, P \rangle[/math]. В качестве нетерминалов будем использовать конструкции вида [math][pXq][/math] (где [math] p, q \in Q[/math], [math]X \in \Pi[/math]), которая неформально означает, что в процессе изменения состояния автомата от [math]p[/math] до [math]q[/math] символ [math]X[/math] удаляется с вершины стека, не затрагивая то, что находится ниже. Также введём стартовый нетерминал [math]S[/math]. Таким образом, [math]N = Q \times \Pi \times Q \cup S[/math].

Правила вывода [math]P[/math] построим следующим образом:

  • для каждого состояния [math]p \in Q[/math] добавим правило [math]S \rightarrow [q_0 z_0 p][/math];
  • для каждого перехода [math](r_0, \gamma_1 \gamma_2 \ldots \gamma_k) \in \delta(p, a, X)[/math] сделаем следующее: для всех упорядоченных списков состояний [math][r_1, r_2 \ldots r_k] \in Q^k[/math] добавим правило [math][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][/math], если [math]k \gt 0[/math], и [math][p X r_0] \rightarrow a[/math], если [math]k = 0[/math].

Нетерминал [math][pXq][/math] должен выводить только те строки [math]w[/math], которые переводят автомат из состояния [math](p, X)[/math] в [math](q, \varepsilon)[/math]. Формально это можно записать следующим образом: [math][pXq] \Rightarrow^* w \iff (p, w, X) \vdash^* (q, \varepsilon, \varepsilon)[/math]. Докажем это утверждение:

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

Пример[править]

Пусть у нас имеется МП-автомат [math]A = \langle \{i,e\}, \{Z\}, \{q\}, q, Z, \delta \rangle[/math], функция [math]\delta[/math] задана следующим образом:

[math]\delta(q, i, Z) = \{(q, ZZ)\}[/math]
[math]\delta(q, e, Z) = \{(q, \varepsilon)\}[/math]

Example2.png

Так как стековый алфавит [math]A[/math] содержит лишь один символ и одно состояние, то в построенной грамматике будет лишь 2 нетерминала:

  • [math]S[/math] — стартовый нетерминал.
  • [math][qZq][/math] — единственная тройка, которую можно собрать из состояний автомата и символов стекового алфавита.

Также грамматика имеет следующие правила вывода:

  • Единственной продукцией для [math]S[/math] является [math]S \rightarrow [qZq][/math]. Но если бы у автомата было [math]n[/math] состояний, то тут бы имелось и [math]n[/math] продукций.
  • Из того факта, что [math]\delta(q, i, Z)[/math] содержит [math](q, ZZ)[/math], получаем правило вывода [math][qZq] \rightarrow i[qZq][qZq][/math]. Если бы у автомата было [math]n[/math] состояний, то такой переход порождал бы [math]n^2[/math] продукций.
  • Из [math]\delta(q,e,Z)=\{(q,\varepsilon)\}[/math] получаем правило вывода [math][qZq] \rightarrow e[/math]

Для удобства тройку [math][qZq][/math] можно заменить символом [math]A[/math], в таком случае правила вывода в грамматике будут следующие:

[math]S \rightarrow A[/math]
[math]A \rightarrow iAA[/math]
[math]A \rightarrow e[/math]

Упростим грамматику, заменив [math]A[/math] на [math]S[/math] (очевидно, она не поменяется), и получим в результате [math]\Gamma = \langle\{i,e\}, \{S\}, S, \{S \rightarrow iSS | e\}\rangle[/math]

Эквивалентность языков МП-автоматов и КС-языков[править]

Теорема (об эквивалентности языков МП-автоматов и КС-языков):
Множество языков, допускаемых МП-автоматами, совпадает с множеством контекстно-свободных языков.
Доказательство:
[math]\triangleright[/math]
Первая теорема гласит, что [math] \mathrm{CFG} \subseteq \mathrm{PDA} [/math], а вторая — что [math] \mathrm{PDA} \subseteq \mathrm{CFG} [/math]. Таким образом, [math] \mathrm{PDA} = \mathrm{CFG} [/math].
[math]\triangleleft[/math]

Следствия[править]

Утверждение:
Для любого МП-автомата с допуском по пустому стеку существует эквивалентный МП-автомат с одним состоянием.
[math]\triangleright[/math]
Построим КС-грамматику по данному автомату, затем по полученной грамматике построим МП-автомат, как указано выше. Заметим, что этот автомат будет иметь одно состояние, что и требовалось доказать.
[math]\triangleleft[/math]
Утверждение:
Для любого МП-автомата с допуском по пустому стеку существует эквивалентный МП-автомат, в любом переходе которого на стек кладётся не больше двух символов.
[math]\triangleright[/math]
Построим КС-грамматику по данному автомату и приведём её к нормальной форме Хомского. Затем по полученной грамматике построим МП-автомат, как указано выше. Заметим, что в нормальной форме Хомского правые части всех правил имеют длину не больше двух, поэтому в любом переходе в полученном автомате на стек кладётся не больше двух символов.
[math]\triangleleft[/math]
Утверждение:
Для любого МП-автомата существует эквивалентный МП-автомат с допуском по пустому стеку без [math]\varepsilon[/math]-переходов.
[math]\triangleright[/math]
Построим КС-грамматику по данному автомату, затем по полученной грамматике построим МП-автомат, как указано выше. Заметим, что этот автомат не будет иметь [math]\varepsilon[/math]-переходов, что и требовалось доказать.
[math]\triangleleft[/math]

См. также[править]

Источники информации[править]

  • Wikipedia — PDA and context-free languages
  • Введение в теорию автоматов, языков и вычислений / Хопкрофт Д., Мотвани Р., Ульман Д. — М.:Издательский дом «Вильямс», 2002. с. 251. — ISBN 5-8459-0261-4