Изменения

|definition=Грамматика имеет '''порядок n''', если <tex>|\alpha| <= n </tex> и <tex>|\beta| <= n </tex> для любого ее правила <tex>\alpha \rightarrow \beta</tex>.

Для любой грамматики <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| <= |\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| <= 2, |\beta| <= 2 \},P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| >= 2, |\beta| >= 3 \},P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| </tex>= 3 \}.Очевидно, что P = P_1 U P_2 U P_3.

Построим G' следующим образом:* Если правило p <tex>P_2 = \in P_2, то оно имеет вид AB{ \alpha' \rightarrow CDE\beta', где | \alpha' \in N^* и rightarrow \beta' \in N^*. Полагаем N_p = \{ A_pP, B_p \}, P_p = \{ AB \rightarrow A_pB_p, A_p \rightarrow C, B_p|\alpha' \rightarrow DE\beta'}, где A_p, B_p {{---}} дополнительные символы не из N: {A_p, B_p) пересечь {A_q, B_q} | >= 0 для разных правил p и q из P_2.* Если правило p \in P_32, то оно имеет вид A \rightarrow CDE\beta', где |\beta' \int N^*. Полагаем N_p = \{B_p \}, P_p | >= \{A \rightarrow CB_p, B_p \rightarrow DE\beta'3 \}</tex>, где A_p, B_p {{---}} дополнительные символы.

<tex>P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| >= 3 \}</tex>. Очевидно, что <tex>P = P_1 \cup P_2 \cup P_3</tex>. Построим <tex>G'</tex> следующим образом:* Если правило <tex>p \in P_2</tex>, то оно имеет вид <tex>AB\alpha' \rightarrow CDE\beta'</tex>, где <tex>\alpha' \in N^*</tex> и <tex>\beta' \in N^*</tex>. Полагаем <tex>N_p = \{ A_p, B_p \}</tex>, <tex>P_p = \{ AB \rightarrow A_pB_p, A_p \rightarrow C, B_p\alpha' \rightarrow DE\beta'\}</tex>, где <tex>A_p, B_p</tex> {{---}} дополнительные символы не из <tex>N: \{A_p, B_p\} \cap \{A_q, B_q\} = 0</tex> для разных правил <tex>p</tex> и <tex>q</tex> из <tex>P_2</tex>. * Если правило <tex>p \in P_3</tex>, то оно имеет вид <tex>A \rightarrow CDE\beta'</tex>, где <tex>\beta' \in N^*</tex>. Полагаем <tex>N_p = \{B_p \}</tex>, <tex>P_p = \{A \rightarrow CB_p, B_p \rightarrow DE\beta'\}</tex>, где <tex>A_p, B_p</tex> {{---}} дополнительные символы. Тогда <tex>N' = N U (объединение по P из \bigcup_{p \in (P_2 U \cup P_3) } N_p)</tex>, <tex>P' = P_1 U (объединение по P из \bigcup_{p \in (P_2 U \cup P_3) } P_p)</tex>. Из построения очевидно, что <tex>G' </tex> имеет порядок <tex>n - 1</tex>.