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

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

Пусть дана КС-грамматика [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]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] I \rightarrow a|b|I1|I0|Ia|Ib [/math],
• [math] E \rightarrow I|E*E|E+E|(E) [/math].

Множеством входных символов является [math] \{a,b,1,0,(,),+,*\} [/math]. Эти символы вместе с переменными [math] I,E [/math] образуют магазинный алфавит. Функция переходов определена следующим образом:

• a) [math] \delta(q,\varepsilon,I)={(q,a), (q,b), (q,Ia), (q,Ib), (q,I0), (q,I1)};[/math]
• b) [math] \delta(q,\varepsilon,E)={(q,I), (q,E+E), (q,E*E), (q,(E))};[/math]
• c) [math] \delta(q,a,a)=\{(q,\varepsilon)\}[/math]; [math] \delta(q,b,b)=\{(q,\varepsilon)\}[/math];...[math] \delta(q,*,*)=\{(q,\varepsilon)\}[/math]. Если входной символ совпадает с вершиной стека, то вершина удаляется.

Пункты a,b образованы по первому правилу построения функции переходов, а пункт c по второму.

Корректность построения

Покажем, что язык, допускаемый автоматом [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]N \Rightarrow^* x[/math]
  • База (1 переход):
    Если [math](q, x, N) \vdash (q, \varepsilon, \varepsilon)[/math], то [math]x = \varepsilon[/math] и в грамматике присутствует правило [math]N \rightarrow \varepsilon[/math], по которому выводится [math]\varepsilon = x[/math].
  • Индукционный переход:
    Предположим, что автомат [math]A[/math] совершает [math]n[/math] шагов ([math]n \gt 1[/math]). Изначально на вершине стеке находится [math]S[/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] и <texY_i</tex>. Значит, [math]Y_i \Rightarrow^* x_i[/math] за 0 шагов.
    Таким образом, получаем, что [math]N \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]N[/math], получаем, что [math]S \Rightarrow^* w[/math]

Теорема:

Класс контекстно-свободных языков ([math]\mathrm{CFG}[/math]) является подмножеством класса языков, задаваемых автоматами с магазинной памятью ([math]\mathrm{PDA}[/math]).

Доказательство:

[math]\triangleright[/math]

Выше показано, что по любой КС-грамматике можно построить МП-автомат, задающий тот же язык, что и исходная грамматика. Утверждение теоремы непосредственно следует из данного факта.

[math]\triangleleft[/math]

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

Наша конструкция эквивалентной грамматики использует переменные вида: [math] [pXq][/math] — которая означает, что в процессе изменения состояния автомата от [math] p [/math] до [math] q [/math], [math] X [/math] удалилось из стека.

Следует отметить, что удаление [math] X [/math] может являться результатом множества переходов.
Пусть [math] P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0)[/math] — МП-автомат. Построим [math] G=(V,\Sigma,R,S)[/math], где [math] V [/math] состоит из:

• 1 Специальный стартовый символ [math] S [/math],
• 2 Все символы вида [math] [pXq][/math], где [math] p [/math] и [math] q [/math] — состояния из [math] Q [/math], а [math] X [/math] — магазинный символ из [math] \Gamma [/math].

Грамматика [math] G [/math] имеет следующие продукции:

• a) продукции [math] S \rightarrow [q_0Z_0p] [/math] для всех [math] p [/math], таким образом [math] (q,w,Z_0)\vdash^* (q,\varepsilon,\varepsilon)[/math]
• b) пусть [math] \delta(q,a,X) [/math] содержит [math] (r,Y_1Y_2...Y_k)[/math]. Тогда для всех списков состояний [math] r_1,r_2,...,r_k[/math] в грамматике [math] G [/math] есть продукция [math] [qXr_k]\rightarrow a[r Y_1 r_1][r_1 Y_1 r_2]...[r_{k-1} Y_k r_k][/math].

Пример

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

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

Так как [math] P [/math] имеет один магазинный символ и одно состояние, то грамматика строится просто. У нас будет всего две переменные:

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

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

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

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

• [math] S \rightarrow A[/math]
• [math] A \rightarrow iAA | \varepsilon[/math]

В действительности можно заметить, что [math]S[/math] и [math]A[/math] порождают одни и те же цепочки, поэтому их можно обозначить одинаково, итого: [math] G=(\{S\},\{i,e\},\{S \rightarrow iSS| \varepsilon\},S)[/math]

Корректность построения

Докажем, что если [math] (q,w,X) \vdash^* (p,\varepsilon,\varepsilon)[/math], то [math] [qXp] \Rightarrow^* w [/math].

• База. Пара [math] (p,\varepsilon) [/math] должна быть в [math] \delta(q,w,X) [/math] и [math] w [/math] есть одиночный символ, или [math]\varepsilon[/math]. Из построения [math] G [/math] следует, что [math] [qXp] \rightarrow w [/math] является продукцией, поэтому [math] [qXp] \Rightarrow w [/math].
• Переход. Предположим, что последовательность [math] (q,w,X) \vdash^* (p,\varepsilon,\varepsilon)[/math] состоит из [math] n [/math] переходов, и [math] n\gt 1 [/math]. Первый переход должен иметь вид:

[math] (q,w,Z) \vdash (r_0,X,Y_1Y_2...Y_k) \vdash^* (p,\varepsilon,\varepsilon) [/math], где [math] w=aX [/math] для некоторого [math] a [/math], которое является либо символом из [math] \Gamma [/math], либо [math] \varepsilon [/math]. По построению [math] G [/math] существует продукция [math] [qXr_k] \rightarrow a[r_0 Y_1 r_1][r_1 Y_2 r_2]...[r_{k-1} Y_k r_k] [/math], где [math] r_i[/math] — состояния из [math] Q [/math], и [math] r_k = p [/math]. Пусть [math] X=w_1 w_2 ... w_k [/math], где [math] w_i [/math] — входная цепочка, которая прочитывается до удаления [math] Y_i [/math] из стека, тогда [math] (r_{i-1},w_i, Y_i) \vdash^* (r_i, \varepsilon, \varepsilon)[/math]. По скольку ни одна из этих последовательностей переходов не содержит более, чем [math] n [/math] переходов, к ним можно применить предположение индукции [math] [r_{i-1}Y_ir_i] \Rightarrow^* w_i[/math]. Соберем эти порождения вместе:
[math] [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[/math].

Теорема:

Класс языков, задаваемых автоматами с магазинной памятью ([math]\mathrm{PDA}[/math]), является подмножеством класса контекстно-свободных языков ([math]\mathrm{CFG}[/math]).

Доказательство:

[math]\triangleright[/math]

Выше показано, что по любму МП-автомату можно построить КС-грамматику, задающую тот же язык, что и допускаемый автоматом. Утверждение теоремы непосредственно следует из данного факта.

[math]\triangleleft[/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]

Литература

• Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 251.