|statement=Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах.
|proof=
АРВАВРассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной ослабленной форме Грейбах нужно выполнить несколько шагов. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>. #Избавимся от <tex> \varepsilon </tex>-правил. Для этого воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления ε-правил]]. Получим грамматику <tex> \Gamma_1 </tex>.#Воспользуемся [[Устранение_левой_рекурсии|алгоритмом устранения левой рекурсии]]. #:Получим грамматику <tex> \Gamma_2 </tex>, все правила которой будут иметь следующий вид:#:*<tex> A_i \rightarrow a \gamma </tex>,#:*<tex> A_i \rightarrow A_j \gamma </tex>,#:где <tex> A_i </tex>, <tex> A_j </tex> {{---}} нетерминалы, <tex> a </tex> {{---}} терминал, <tex> \gamma </tex> {{---}} произвольная последовательность из терминалов и нетерминалов, <tex> i < j </tex>.#
}}
