Изменения
Нет описания правки
Пусть <tex>N' = N \cup \{a' | a \in T\}</tex>.
Пусть <tex>\alpha = x_1x_2...x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2...y_n</tex>, где <tex>y_i = \{x_i</tex>, если <tex>x_i \in N</tex>; <tex>x_i'</tex>, если <tex>x_i \in T\}</tex> для <tex>1 <= \leqslant i <= \leqslant n</tex>.
Построим грамматику <tex>G' = (N', T, P', S)</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: a \in T\}</tex>.
Согласно конструкции <tex>P'</tex>, в <tex>G'</tex> существует вывод <tex>S = w_0' => w_1' => w_2' => ... => w_n' = v_0 => v_1 => v_2 => ... => v_m = w</tex>.
Для <tex>0 <= \leqslant i <= \leqslant n - 1</tex> в переходах <tex>w_i' => w_{i + 1}'</tex> используем правило <tex>\alpha' \rightarrow \beta'</tex>, так как правило <tex>\alpha \rightarrow \beta</tex> было использовано при выводе <tex>w_i => w_{i + 1}</tex>.
Для <tex>0 <= \leqslant j <= \leqslant m - 1</tex> в переходах <tex>v_j => v_{j + 1}</tex> используем правила вида <tex>a' \rightarrow a</tex>.
Заменяем разрешенные в <tex>w'</tex> символы на новые и получаем, что <tex>w \in L(G')</tex>.
Из построения: после применения правила вида <tex>a' \rightarrow a</tex> полученное <tex>a</tex> не может быть использовано при применении правил из <tex>P'</tex>.
Изменение порядка вывода не меняет язык, то есть в <tex>G'</tex> существует вывод: <tex>S = x_0' => x_1' => ... => x_r' => x' => y_1 => y_2 => ... => y_s = x</tex>, где для <tex>0 <= \leqslant i <= \leqslant r - 1 x_{i + 1}' \in (N')^*</tex> и в переходе <tex>x_i' \rightarrow x_{i + 1}'</tex> было использовано правило вывода <tex>\alpha' \rightarrow \beta'</tex> и для <tex>1 <= \leqslant j <= \leqslant s</tex> было использовано правило <tex>a' \rightarrow a</tex>, чтобы получить <tex>y_j \rightarrow y_{j + 1}</tex>.
Получаем вывод в <tex>G</tex>: <tex>S = x_0 => x_1 => ... => x_n = x</tex>.
|about=об удалении длинных правил
|statement= Для любой грамматики <tex>G = (N, T, P, S)</tex> может быть построена грамматика <tex>G' = (N', T, P', S)</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=
{{Определение
|definition=Грамматика имеет '''порядок n''', если <tex>|\alpha| <= \leqslant n</tex> и <tex>|\beta| <= \leqslant n</tex> для любого ее правила <tex>\alpha \rightarrow \beta</tex>.
}}
|about=об уменьшении порядка грамматики
|statement=(Уменьшение порядка грамматики)
Для любой грамматики <tex>G = (N, T, P, S)</tex> порядка <tex>n >= 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' = (N', T, P', S)</tex> порядка <tex>n - 1</tex> такая, что <tex>L(G') = L(G)</tex>.
|proof=
Разделим <tex>P</tex> на три подмножества:
<tex>P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| <= \leqslant 2, |\beta| <= \leqslant 2 \}</tex>,
<tex>P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| >= 2, |\beta| >= 3 \}</tex>,
