Изменения
Нет описания правки
|about=об уменьшении порядка грамматики
|statement=(Уменьшение порядка грамматики)
Для любой грамматики <tex>G = (N, T, P, S)</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' = (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| >= \geqslant 2, |\beta| >= \geqslant 3 \}</tex>,
<tex>P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| >= \geqslant 3 \}</tex>.
Очевидно, что <tex>P = P_1 \cup P_2 \cup P_3</tex>.
Пусть <tex>G''</tex> имеет порядок <tex>n</tex>.
Если <tex>n = 2</tex>, то <tex>G''</tex> в нормальной форме Куроды и <tex>G_K = G''</tex>.
Если <tex>n >= \geqslant 3</tex>, построим <tex>G'''</tex> порядка <tex>n - 1</tex> из <tex>G''</tex> по лемме 3.
Понятно, что <tex>G'''</tex> удовлетворяет условиям леммы 3.
Будем повторять процесс, пока не получим грамматику порядка <tex>2</tex>, которую и примем за <tex>G_K</tex>.
}}
