Изменения

|definition=[[Формальные грамматики|Грамматика ]] представлена в '''нормальной форме Куроды''' (англ. ''Kuroda normal form''), если каждое правило имеет одну из четырех форм:

# <tex>AB \rightarrow CDAC</tex>

Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.

|statement = Для любой грамматики <tex>G \Gamma = (\langle \Sigma, N, TS, P, S)\rangle</tex> может быть построена грамматика <tex>G\Gamma' = (\langle \Sigma, N', TS, P', S)\rangle</tex> такая, что:* все правила в <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex> где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^*</tex> или <tex>A \rightarrow a</tex>, где <tex>A \in N', a \in T\Sigma</tex>,* <tex>L(G\Gamma') = L(G\Gamma)</tex>Кроме того, если G <tex>\Gamma</tex> контекстно-свободна или контекстно-зависима, то и <tex>G\Gamma'</tex> будет соответственно контекстно-свободной или контекстно-зависимой.

|proof = Каждому терминалу <tex>a</tex> поставим в соотвествие новый символ <tex>a'</tex>, которого нет в <tex>N \cup T\Sigma</tex>, такой что <tex>a' \neq b'</tex> для разных терминалов <tex>a</tex> и <tex>b</tex>.

Пусть <tex>N' = N \cup \{a' | \mid a \in T\Sigma\}</tex>.

Пусть <tex>\alpha = x_1x_2...\ldots x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2...\ldots y_n</tex>, где <tex>y_i = \left\{\begin{array}{llcl}x_i</tex>, если <tex>&;\ x_i \in N</tex>; <tex>\\x_i'</tex>, если <tex>&;\ x_i \in T\Sigma\\\end{array}\right.</tex> для <tex>1 <= \leqslant i <= \leqslant n</tex>.

Построим грамматику <tex>G' = (\langle \Sigma, N', TS, P', S)\rangle</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' : \mid \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: \mid a \in T\Sigma\}</tex>.

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

Пусть <tex>w \in L(G\Gamma)</tex>. Тогда в G <tex>\Gamma</tex> существует вывод <tex>S = w_0 => \Rightarrow w_1 => ... => \Rightarrow \ldots \Rightarrow w_n => \Rightarrow w</tex>.

Согласно конструкции <tex>P'</tex>, в <tex>G\Gamma'</tex> существует вывод <tex>S = w_0' => \Rightarrow w_1' => \Rightarrow w_2' => ... => \Rightarrow \ldots \Rightarrow w_n' = v_0 => \Rightarrow v_1 => \Rightarrow v_2 => ... => \Rightarrow \ldots \Rightarrow v_m = w</tex>.

Для <tex>0 <= \leqslant i <= \leqslant n - 1</tex> в переходах <tex>w_i' => \Rightarrow w_{i + 1}'</tex> используем правило <tex>\alpha' \rightarrow \beta'</tex>, так как правило <tex>\alpha \rightarrow \beta</tex> было использовано при выводе <tex>w_i => \Rightarrow w_{i + 1}</tex>.

Для <tex>0 <= \leqslant j <= \leqslant m - 1</tex> в переходах <tex>v_j => \Rightarrow v_{j + 1}</tex> используем правила вида <tex>a' \rightarrow a</tex>.

Заменяем разрешенные в <tex>w'</tex> символы на новые и получаем, что <tex>w \in L(G\Gamma')</tex>.Тогда <tex>L(G\Gamma) <= \subseteq L(G\Gamma')</tex>.

Пусть <tex>x \in L(G\Gamma')</tex>. Тогда в <tex>G\Gamma'</tex> существует вывод <tex>S =>\Rightarrow^* x</tex>. Мы можем поменять порядок применения правил в этом выводе: сначала применяем только правила вида <tex>\alpha' \rightarrow \beta'</tex>, а потом только правила вида <tex>a' \rightarrow a</tex>.

Изменение порядка вывода не меняет язык, то есть в <tex>G\Gamma'</tex> существует вывод: <tex>S = x_0' => \Rightarrow x_1' => ... => \Rightarrow \ldots \Rightarrow x_r' => \Rightarrow x' => \Rightarrow y_1 => \Rightarrow y_2 => ... => \Rightarrow \ldots \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\Gamma</tex>: <tex>S = x_0 => \Rightarrow x_1 => ... => \Rightarrow \ldots \Rightarrow x_n = x</tex>.

Тогда <tex>L(G\Gamma') <= \subseteq L(G\Gamma)</tex>.

Таким образом, <tex>L(G\Gamma') = L(G\Gamma)</tex>.

|about=об удалении длинных коротких правил|statement= Для любой грамматики <tex>G \Gamma = (\langle \Sigma, N, TS, P, S)\rangle</tex> может быть построена грамматика <tex>G\Gamma' = (\langle \Sigma, N', TS, P', S)\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\Gamma') = L(G\Gamma)</tex>

Сначала по <tex>G\Gamma</tex> построим грамматику <tex>G\Gamma'' = (\langle \Sigma, N'', TS, P'', S)\rangle</tex>, как в доказательстве леммы 1. По <tex>G\Gamma''</tex> построим грамматику <tex>G\Gamma'</tex>, в которой:

Покажем, что <tex>L(G\Gamma') = L(G\Gamma)</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\Gamma) <= \subseteq L(G\Gamma')</tex>, аналогично обратные изменения не меняют язык, то есть <tex>L(G\Gamma') <= \subseteq L(G\Gamma)</tex>.

|definition=Грамматика имеет '''порядок <tex>n</tex>''', если <tex>|\alpha| <= \leqslant n</tex> и <tex>|\beta| <= \leqslant n</tex> для любого ее правила <tex>\alpha \rightarrow \beta</tex>.

|statement=(Уменьшение порядка грамматики)Для любой грамматики <tex>G \Gamma = (\langle \Sigma, N, TS, P, S)\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\Gamma' = (\langle \Sigma, N', TS, P', S)\rangle</tex> порядка <tex>n - 1</tex> такая, что <tex>L(G\Gamma') = L(G\Gamma)</tex>.

<tex>P_2 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>G\Gamma'</tex> следующим образом:

Тогда <tex>N' = N \bigcup_bigcup\limits_{p \in (P_2 \cup P_3)} N_p</tex>, <tex>P' = P_1 \bigcup_bigcup\limits_{p \in (P_2 \cup P_3)} P_p</tex>. Из построения очевидно, что <tex>\Gamma'</tex> имеет порядок <tex>n - 1</tex>. Покажем, что <tex>L(\Gamma') = L(\Gamma)</tex>. Сначала докажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. Это следует из того, что:* все правила из <tex>P_1</tex> применимы к обеим грамматикам, * шаг вывода <tex>\gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1CDE\beta'\gamma_2</tex>, благодаря правилу <tex>p = AB\alpha \rightarrow CDE\beta' \in P_2</tex> в <tex>\Gamma</tex>может быть использавано в <tex>\Gamma'</tex> с помощью трех шагов:<tex>\gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 \Rightarrow \gamma_1CB_p\alpha'\gamma_2 \Rightarrow \gamma_1CDE\beta\gamma_2</tex>, с использованием правил из <tex>P_p</tex> и вывода <tex>\gamma_1A\gamma_2 \Rightarrow \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 \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 \Rightarrow \gamma_1CB_p\alpha'\gamma_2 \Rightarrow \gamma_1CDE\beta\gamma_2</tex>.Таким образом, любой вывод в <tex>\Gamma</tex> может быть преобразован в вывод в <tex>\Gamma'</tex>. Чтобы показать обратное включение, рассмотрим вывод <tex>w \in L(\Gamma')</tex> в <tex>\Gamma'</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): <tex>S \Rightarrow^* \gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 \Rightarrow^{q_1} \gamma_1'A_pB_p\alpha'\gamma_2' \Rightarrow \gamma_1'CB_p\alpha'\gamma_2' \Rightarrow^{q_2} \gamma_1''B_p\alpha'\gamma_2'' \Rightarrow \gamma_1''DE\beta'\gamma_2'' \Rightarrow^* w \in T^*</tex>, где <tex>q_1</tex> {{---}} последовательность правил, примененых после <tex>AB \rightarrow A_pB_p</tex> и до <tex>A_p \rightarrow C</tex>, которая осуществляет <tex>\gamma_1 \Rightarrow^* \gamma_1'</tex> и <tex>\gamma_2 \Rightarrow^* \gamma_2'</tex>, где <tex>q_2</tex> {{---}} последовательность правил, осуществляющих <tex>\gamma_1'C \Rightarrow^* \gamma_1''</tex> и <tex>\gamma_2' \Rightarrow^* \gamma_2''</tex>.

Покажем<tex>S \Rightarrow^* \gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 \Rightarrow^{q_1'} \gamma_1' A_p B_p \alpha' \gamma_2' \Rightarrow \gamma_1'A_pDE\beta'\alpha'\gamma_2' \Rightarrow^{q_2'} \gamma_1''A_p\gamma_2'' \Rightarrow \gamma_1''C\gamma_2'' \Rightarrow^* w \in T^*</tex>, что L(G') = L(G).

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

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

Или (2) Таким образом, существует вывод: <tex>S =>\Rightarrow^* \gamma_1AB\alpha'\gamma_2 => \gamma_1A_pB_pRightarrow \gamma_1CDE\alphabeta'\gamma_2 =>(\Rightarrow^{q_1') } \gamma_1'A_pB_pCDE\alphabeta'\gamma_2' => \gamma_1'A_pDE\beta'\alpha'\gamma_2' =>(Rightarrow^{q_2') } \gamma_1''A_pDE\gamma_2beta'' => \gamma_1gamma_2''C\gamma_2'' =>Rightarrow^* w \in T^*</tex>,где q_1' {{---}} последовательность который получается из (1) заменой правил, которая осуществляет \gamma_1 <tex>P_p</tex> на применение <tex>p =>* AB\gamma_1alpha' \rightarrow CDE\beta \in P</tex>. Аналогично, в случае (2) мы можем заменить применение <tex>P_p</tex> на <tex>p</tex>. Кроме того, это верно и для применения <tex>P_q,</tex> где <tex>q \gamma_2 =in P_3</tex>* \gamma_2',. где q_2' {{---}} последовательность правилТаким образом, осуществляющих \gamma_1' =для <tex>* r \gamma_1'' и DEin P_2 \beta'\gamma_2' =cup P_3</tex> мы можем заменить все применения <tex>P_r</tex> на <tex>r</tex>, то есть получаем вывод <tex>w</tex>, который состоит только из правил из <tex>P</tex>* \gamma_2''.

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

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

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