Изменения
Нет описания правки
{{Лемма
|about=об удалении терминалов
|statement = Для любой грамматики <tex>G = (\langle \Sigma, N, TS, P, S)\rangle</tex> может быть построена грамматика <tex>G' = (\langle \Sigma, N', TS, P', S)\rangle</tex> такая, что:* все правила в <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex> где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^*</tex> или <tex>A \rightarrow a</tex>, где <tex>A \in N', a \in T\Sigma</tex>,
* <tex>L(G') = L(G)</tex>
Кроме того, если G контекстно-свободна или контекстно-зависима, то и <tex>G'</tex> будет соответственно контекстно-свободной или контекстно-зависимой.
|proof = Каждому терминалу <tex>a</tex> поставим в соотвествие новый символ <tex>a'</tex>, которого нет в <tex>N \cup T\Sigma</tex>, такой что <tex>a' \neq b'</tex> для разных терминалов <tex>a</tex> и <tex>b</tex>.
Пусть <tex>N' = N \cup \{a' : a \in T\Sigma\}</tex>.
Пусть <tex>\alpha = x_1x_2...x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2...y_n</tex>, где
y_i = \left\{\begin{array}{llcl}
x_i&;\ x_i \in N\\
x_i'&;\ x_i \in T\Sigma\\
\end{array}\right.
</tex> для <tex>1 \leqslant i \leqslant n</tex>.
Построим грамматику <tex>G' = (\langle \Sigma, N', TS, P', S)\rangle</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: a \in T\Sigma\}</tex>.
Покажем, что <tex>L(G') = L(G)</tex>.
Пусть <tex>w \in L(G)</tex>. Тогда в <tex>G </tex> существует вывод <tex>S = w_0 \Rightarrow w_1 \Rightarrow ... \Rightarrow w_n \Rightarrow w</tex>.
Согласно конструкции <tex>P'</tex>, в <tex>G'</tex> существует вывод <tex>S = w_0' \Rightarrow w_1' \Rightarrow w_2' \Rightarrow ... \Rightarrow w_n' = v_0 \Rightarrow v_1 \Rightarrow v_2 \Rightarrow ... \Rightarrow v_m = w</tex>.
{{Лемма
|about=об удалении длинных правил
|statement= Для любой грамматики <tex>G = (\langle \Sigma, N, TS, P, S)\rangle</tex> может быть построена грамматика <tex>G' = (\langle \Sigma, N', TS, P', S)\rangle</tex> такая, что:
* любое правило из <tex>P'</tex> имеет вид: <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^+</tex> и <tex>|\alpha| \leqslant |\beta|</tex>, или <tex>A \rightarrow a</tex>, или <tex>A \rightarrow \varepsilon</tex>, где <tex>A \in N'</tex> и <tex>a \in T</tex>
* <tex>L(G') = L(G)</tex>
|proof=
Сначала по <tex>G</tex> построим грамматику <tex>G'' = (\langle \Sigma, N'', TS, P'', S)\rangle</tex>, как в доказательстве леммы 1. По <tex>G''</tex> построим грамматику <tex>G'</tex>, в которой:
* <tex>N' = N'' \cup \{D\}</tex>, где <tex>D</tex> {{---}} новый символ,
* <tex>P'</tex> получаем из <tex>P''</tex> заменой всех правил вида <tex>\alpha \rightarrow \beta \in P''</tex>, где <tex>|\alpha| > |\beta|</tex> на правила вида <tex>\alpha \rightarrow \beta D^{|\alpha| - |\beta|}</tex>, и добавлением правила <tex>D \rightarrow \varepsilon</tex>.
|about=об уменьшении порядка грамматики
|statement=(Уменьшение порядка грамматики)
Для любой грамматики <tex>G = (\langle \Sigma, N, TS, P, S)\rangle</tex> порядка <tex>n \geqslant 3</tex>, такой что: любое правило из <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^+</tex> и <tex>|\alpha| \leqslant |\beta|</tex> или <tex>A \rightarrow a</tex> или <tex>A \rightarrow \varepsilon</tex>, где <tex>A \in N'</tex> и <tex>a \in T</tex> может быть построена грамматика <tex>G' = (\langle \Sigma, N', TS, P', S)\rangle</tex> порядка <tex>n - 1</tex> такая, что <tex>L(G') = L(G)</tex>.
|proof=
Разделим <tex>P</tex> на три подмножества:
