Изменения
Нет описания правки
|proof = Каждому терминалу <tex>a</tex> поставим в соотвествие новый символ <tex>a'</tex>, которого нет в <tex>N \cup \Sigma</tex>, такой что <tex>a' \neq b'</tex> для разных терминалов <tex>a</tex> и <tex>b</tex>.
Пусть <tex>N' = N \cup \{a' : \mid a \in \Sigma\}</tex>.
Пусть <tex>\alpha = x_1x_2...x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2...y_n</tex>, где
</tex> для <tex>1 \leqslant i \leqslant n</tex>.
Построим грамматику <tex>G' = \langle \Sigma, N', S, P' \rangle</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' : \mid \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: \mid a \in \Sigma\}</tex>.
Покажем, что <tex>L(G') = L(G)</tex>.
Разделим <tex>P</tex> на три подмножества:
<tex>P_1 = \{ \alpha \rightarrow \beta | \mid \alpha \rightarrow \beta \in P, |\alpha| \leqslant 2, |\beta| \leqslant 2 \}</tex>,
<tex>P_2 = \{ \alpha \rightarrow \beta | \mid \alpha \rightarrow \beta \in P, |\alpha| \geqslant 2, |\beta| \geqslant 3 \}</tex>,
<tex>P_3 = \{ \alpha \rightarrow \beta | \mid \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| \geqslant 3 \}</tex>.
Очевидно, что <tex>P = P_1 \cup P_2 \cup P_3</tex>.
