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

Далее будут приведены конструкции для построения МП-автомата по заданной КС-грамматике, и наоборот. Также будет приведена теорема об эквивалентности языков, задаваемых ими.

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

Пусть [math] G=(V,T,Q,S) [/math] — КС-грамматика. Построим МП-автомат [math] P=(\{q\},T,V \cup T, \delta ,q,S) [/math], который допускает [math] L(G) [/math] по пустому магазину. Функция переходов [math] \delta [/math] будет определена по следующим правилам:

• 1. [math] \delta(q,\varepsilon,A)=\{(q,\beta )| A \rightarrow \beta[/math] — продукция [math] G \} [/math] для каждой переменной [math] A [/math].
• 2. [math] \delta(q,a,a)=\{(q,\varepsilon)\} [/math] для каждого терминала [math] a [/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] w\in L(G)[/math], тогда [math] w [/math] имеет следующее левое порождение: [math] S = \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n=w[/math]. Покажем индукцией по [math] i [/math], что [math] (q,w,S)\vdash^*(q,y_i,\alpha_i)[/math]:

• База. Очевидно, что [math] (q,w,S)\vdash^*(q,w,S) [/math].
• Переход. Предположим, что [math] (q,w,S)\vdash^*(q,w_i,\alpha_i) [/math]. Заметим, что шаг порождения [math] y_i \Rightarrow y_{i+1}[/math] включает замену некоторой переменной [math] A [/math] ее продукцией [math] \beta [/math]. Правило 1 построения МП-автомата позволяет на заменить [math] A [/math] на вершине стека на цепочку [math] \beta [/math], а правило 2 позволяет затем сравнить любые терминалы на вершине со входными символами. В результате достигается МО [math] (q,y_{i+1},\alpha_{i+1}) [/math].
• Также заметим, что [math] \alpha_n = \varepsilon[/math]. Таким образом [math] (q,w,S)\vdash^*(q,\varepsilon,\varepsilon) [/math], т.е допускает [math] P [/math] по пустому стеку.

Утверждение (1):

Если МП-автомат [math] P [/math] построен по грамматике [math] G [/math], с использованием указанной выше конструкции, то [math] L(G) \subseteq N(P) [/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].

Утверждение (2):

Если КС-грамматика [math] G [/math] построена по МП-автомату [math] P [/math], с использованием указанной выше конструкции, то [math] N(P) \subseteq L(G) [/math].

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Теорема (Об эквивалентности языков МП-автоматов и КС-языков):

Множество языков, допускаемых МП-автоматами совпадает с множеством языков, задаваемых с помощью контекстно-свободных грамматик.

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

[math]\triangleright[/math]

Из утверждения 1 следует, что [math] L(G) \subseteq N(P) [/math], в свою очередь из утверждения 2 следует, что [math] N(P) \subseteq L(G) [/math]. Отсюда [math] L(G)=N(P) [/math].

[math]\triangleleft[/math]

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.