Изменения

Покажем, что <tex>L(G') = L(G)</tex>.

Сначала докажем, что <tex>L(G) <= L(G')</tex>. Это следует из того, что:* все правила из <tex>P_1 </tex> применимы к обеим грамматикам, * шаг вывода <tex>\gamma_1AB\alpha'\gamma_2 => \gamma_1CDE\beta'\gamma_2</tex>, благодаря правилу <tex>p = AB\alpha \rightarrow CDE\beta' \in P_2 </tex> в <tex>G, </tex>может быть использавано в <tex>G' </tex> с помощью трех шагов:<tex>\gamma_1AB\alpha'\gamma_2 => \gamma_1A_pB_p\alpha'\gamma_2 => \gamma_1CB_p\alpha'\gamma_2 => \gamma_1CDE\beta\gamma_2</tex>, с использованием правил из <tex>P_p </tex> и вывода <tex>\gamma_1A\gamma_2 => \gamma_1CDE\beta'\gamma_2 </tex> на основе правила <tex>p = A\alpha \rightarrow CDE\beta' \in P_3 </tex> в <tex>G</tex>, которое может быть применено в <tex>G' </tex> с помощью трех шагов вывода:<tex>\gamma_1A\alpha1'\gamma_2 => \gamma_1A_pB_p\alpha'\gamma_2 => \gamma_1CB_p\alpha'\gamma_2 => \gamma_1CDE\beta\gamma_2</tex>.Таким образом, любой вывод в <tex>G </tex> может быть преобразован в вывод в <tex>G'</tex>.

Чтобы показать обратное включение, рассмотрим вывод <tex>w \in L(G') </tex> в <tex>G'</tex>, который содержит применение правил вида <tex>AB \rightarrow A_pB_p </tex> для какого-то правила <tex>p = AB\alpha' \rightarrow CDE\beta' \in P_2 (</tex>. Заметим, что другие два правила из <tex>P_p </tex> могут быть применены только если правило <tex>AB \rightarrow A_pB_p </tex> было применено в этом выводе ранее).Данный вывод имеет вид:(1) S =>* \gamma_1AB\alpha'\gamma_2 => \gamma_1A_pB_p\alpha'\gamma_2 =>(q_1) \gamma_1'A_pB_p\alpha'\gamma_2' => \gamma_1'CB_p\alpha'\gamma_2' =>(q_2) \gamma_1''B_p\alpha'\gamma_2'' => \gamma_1''DE\beta'\gamma_2'' =>* w \in T^*,где q_1 {{---}} последовательность правил, примененых после AB \rightarrow A_pB_p и до A_p \rightarrow C, которая осуществляет \gamma_1 =>* \gamma_1' и \gamma_2 =>* \gamma_2',где q_2 {{---}} последовательность правил, осуществляющих \gamma_1'C =>* \gamma_1'' и \gamma_2' =>* \gamma_2''.

Данный вывод имеет вид (1) : <tex>S =>* \gamma_1AB\alpha'\gamma_2 => \gamma_1A_pB_p\alpha'\gamma_2 =>(q_1) \gamma_1'A_pB_p\alpha'\gamma_2' => \gamma_1'CB_p\alpha'\gamma_2' =>(q_2) \gamma_1''B_p\alpha'\gamma_2'' => \gamma_1''DE\beta'\gamma_2'' =>* w \in T^*</tex>, где <tex>q_1</tex> {{---}} последовательность правил, примененых после <tex>AB \rightarrow A_pB_p</tex> и до <tex>A_p \rightarrow C</tex>, которая осуществляет <tex>\gamma_1 =>* \gamma_1'</tex> и <tex>\gamma_2 =>* \gamma_2'</tex>, где <tex>q_2</tex> {{---}} последовательность правил, осуществляющих <tex>\gamma_1'C =>* \gamma_1''</tex> и <tex>\gamma_2' =>* \gamma_2''</tex>. Или вид (2) : <tex>S =>* \gamma_1AB\alpha'\gamma_2 => \gamma_1A_pB_p\alpha'\gamma_2 =>(q_1') \gamma_1'A_pB_p\alpha'\gamma_2' => \gamma_1'A_pDE\beta'\alpha'\gamma_2' =>(q_2') \gamma_1''A_p\gamma_2'' => \gamma_1''C\gamma_2'' =>* w \in T^*</tex>, где <tex>q_1' </tex> {{---}} последовательность правил, которая осуществляет <tex>\gamma_1 =>* \gamma_1' </tex> и <tex>\gamma_2 =>* \gamma_2'</tex>, где <tex>q_2' </tex> {{---}} последовательность правил, осуществляющих <tex>\gamma_1' =>* \gamma_1'' </tex> и <tex>DE\beta'\gamma_2' =>* \gamma_2''</tex>.

<tex>S =>* \gamma_1AB\alpha'\gamma_2 => \gamma_1CDE\beta'\gamma_2 => (q_1) \gamma_1'CDE\beta'\gamma_2' => (q_2) \gamma_1''DE\beta'\gamma_2'' =>* w \in T^*</tex>,который получается из (1) заменой правил <tex>P_p </tex> на применение <tex>p = AB\alpha' \rightarrow CDE\beta \in P</tex>. Аналогично, в случае (2) мы можем заменить применение <tex>P_p </tex> на <tex>p</tex>. Кроме того, это верно и для применения <tex>P_q, </tex> где <tex>q \in P_3</tex>. Таким образом, для <tex>r \in P_2 U \cup P_3 </tex> мы можем заменить все применения <tex>P_r </tex> на <tex>r</tex>, то есть получаем вывод <tex>w</tex>, который состоит только из правил из <tex>P</tex>.  Тогда <tex>w \in L(G) </tex> и <tex>L(G') <= L(G)</tex>.

Любую грамматику <tex>G </tex> можно преобразовать к грамматике <tex>G_K </tex> в нормальной форме Куродытак, так что <tex>L(G) = L(G_K)</tex>.

По лемме 1 построим из <tex>G </tex> грамматику <tex>G'</tex>, затем по лемме 2 построим из <tex>G' </tex> грамматику <tex>G''</tex>, Тогда <tex>G'' </tex> удовлетворит требованиям леммы 3. Пусть <tex>G'' </tex> имеет порядок <tex>n</tex>. Нсли Если <tex>n = 2</tex>, то <tex>G'' </tex> в нормальной форме Куроды и <tex>G_K = G''</tex>. Если <tex>n >= 3</tex>, построим <tex>G''' </tex> порядка <tex>n - 1 </tex> из <tex>G'' </tex> по лемме 3.Понятно, что <tex>G''' </tex> удовлетворяет условиям леммы 3, будем . Будем повторять процесс, пока не получим грамматику порядка <tex>2</tex>, которую и примем за <tex>G_K</tex>.