Изменения
Нет описания правки
Из построения: после применения правила вида <tex>a' \rightarrow a</tex> полученное <tex>a</tex> не может быть использовано при применении правил из <tex>P'</tex>.
Изменение порядка вывода не меняет язык, то есть в <tex>G'</tex> существует вывод: <tex>S = x_0' \Rightarrow x_1' \Rightarrow ... \Rightarrow x_r' \Rightarrow x' \Rightarrow y_1 \Rightarrow y_2 \Rightarrow ... \Rightarrow 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 \Rightarrow x_1 \Rightarrow ... \Rightarrow x_n = x</tex>.
{{Лемма
|about=об удалении длинных коротких правил
|statement= Для любой грамматики <tex>G = \langle \Sigma, N, S, P \rangle</tex> может быть построена грамматика <tex>G' = \langle \Sigma, N', S, P' \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>.
Заметим, что замена правила <tex>\alpha \rightarrow \beta</tex> на <tex>\alpha \rightarrow \beta D^{|\alpha| - |\beta|}</tex> не меняет язык грамматики, потому что дополнительная буква <tex>D</tex> запрещается при добавлении перехода переходит только в <tex>D \rightarrow \varepsilon</tex>, а других правил для <tex>D</tex> нет.
Тогда получаем, что <tex>L(G) \subseteq L(G')</tex>, аналогично обратные изменения не меняют язык, то есть <tex>L(G') \subseteq L(G)</tex>.
{{Лемма
|about=об уменьшении порядка грамматики
|statement=(Уменьшение порядка грамматики)
Для любой грамматики <tex>G = \langle \Sigma, N, S, P \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', S, P' \rangle</tex> порядка <tex>n - 1</tex> такая, что <tex>L(G') = L(G)</tex>.
|proof=
* [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах|Приведение грамматики к ослабленной нормальной форме Грейбах]]
== Источники информации ==
* Alexander Meduna Automata and Languages: Theory and Applications
* [[wikipedia:Kuroda_normal_form | Wikipedia {{---}} Kuroda normal form]]
[[Категория: Теория формальных языков]]
