Изменения

|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<= n /tex> и <tex>|\beta| \leqslant n<= n /tex> для любого ее правила <tex>\alpha \rightarrow \beta</tex>.

|statement=(Уменьшение порядка грамматики)Для любой грамматики G <tex>\Gamma = (\langle \Sigma, N, TS, P, S) \rangle</tex> порядка <tex>n \geqslant 3</tex>= 3, такой что: любое правило из <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> может быть построена грамматика G<tex>\Gamma' = (\langle \Sigma, N', TS, P', S) \rangle</tex> порядка <tex>n - 1 </tex> такая, что <tex>L(G\Gamma') = L(G\Gamma)</tex>.|proof= Разделим <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 U \cup P_2 U \cup P_3</tex>. Построим <tex>\Gamma'</tex> следующим образом:* Если правило <tex>p \in P_2</tex>, то оно имеет вид <tex>AB\alpha' \rightarrow CDE\beta'</tex>, где <tex>\alpha' \in N^*</tex> и <tex>\beta' \in N^*</tex>. Полагаем <tex>N_p = \{ A_p, B_p \}</tex>, <tex>P_p = \{ AB \rightarrow A_pB_p, A_p \rightarrow C, B_p\alpha' \rightarrow DE\beta'\}</tex>, где <tex>A_p, B_p</tex> {{---}} дополнительные символы не из <tex>N: \{A_p, B_p\} \cap \{A_q, B_q\} = 0</tex> для разных правил <tex>p</tex> и <tex>q</tex> из <tex>P_2</tex>. * Если правило <tex>p \in P_3</tex>, то оно имеет вид <tex>A \rightarrow CDE\beta'</tex>, где <tex>\beta' \in N^*</tex>.

Построим G' следующим образом:* Если правило p \in P_2, то оно имеет вид AB\alpha' \rightarrow CDE\beta', где \alpha' \in N^* и \beta' \in N^*. Полагаем N_p = \{ A_p, B_p \}, P_p = \{ AB \rightarrow A_pB_p, A_p \rightarrow C, B_p\alpha' \rightarrow DE\beta'}, где A_p, B_p {{---}} дополнительные символы не из N: {A_p, B_p) пересечь {A_q, B_q} = 0 для разных правил p и q из P_2.* Если правило p \in P_3, то оно имеет вид A \rightarrow CDE\beta', где \beta' \int N^*. Полагаем <tex>N_p = \{B_p \}</tex>, <tex>P_p = \{A \rightarrow CB_p, B_p \rightarrow DE\beta'\}</tex>, где <tex>A_p, B_p </tex> {{---}} дополнительные символы.

Тогда <tex>N' = N U (объединение по P из \bigcup\limits_{p \in (P_2 U \cup P_3) } N_p)</tex>, <tex>P' = P_1 U (объединение по P из \bigcup\limits_{p \in (P_2 U \cup P_3) } P_p).Из построения очевидно, что G' имеет порядок n - 1</tex>.

ПокажемИз построения очевидно, что L(G<tex>\Gamma') = L(G)</tex> имеет порядок <tex>n - 1</tex>.

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

Чтобы показать обратное включениеСначала докажем, рассмотрим вывод w что <tex>L(\Gamma) \in subseteq L(G\Gamma') в G</tex>. Это следует из того, что:* все правила из <tex>P_1</tex> применимы к обеим грамматикам, * шаг вывода <tex>\gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1CDE\beta'\gamma_2</tex>, который содержит применение правил вида AB \rightarrow A_pB_p для какого-то правила благодаря правилу <tex>p = AB\alpha' \rightarrow CDE\beta' \in P_2 (Заметим, что другие два правила из P_p могут </tex> в <tex>\Gamma</tex>может быть применены только если правило AB использавано в <tex>\rightarrow A_pB_p было применено в этом выводе ранее).Данный вывод имеет видGamma'</tex> с помощью трех шагов:(1) S =<tex>* \gamma_1AB\alpha'\gamma_2 => \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 =>(q_1) \gamma_1'A_pB_pRightarrow \gamma_1CB_p\alpha'\gamma_2' =\Rightarrow \gamma_1CDE\beta\gamma_2</tex>, с использованием правил из <tex>P_p</tex> и вывода <tex> \gamma_1'CB_pgamma_1A\gamma_2 \Rightarrow \gamma_1CDE\alphabeta'\gamma_2' </tex> на основе правила <tex>p =>(q_2) A\alpha \gamma_1''B_prightarrow CDE\alphabeta'\gamma_2in P_3</tex> в <tex>G</tex>, которое может быть применено в <tex>G'' =</tex> с помощью трех шагов вывода:<tex> \gamma_1''DEgamma_1A\betaalpha1'\gamma_2\Rightarrow \gamma_1A_pB_p\alpha'' =>* w \in T^*,где q_1 {{---}} последовательность правил, примененых после AB gamma_2 \rightarrow A_pB_p и до A_p Rightarrow \rightarrow C, которая осуществляет gamma_1CB_p\gamma_1 =>* \gamma_1alpha' и \gamma_2 =>* \Rightarrow \gamma_1CDE\beta\gamma_2',</tex>.где q_2 {{---}} последовательность правилТаким образом, осуществляющих любой вывод в <tex>\gamma_1'C =Gamma</tex> может быть преобразован в вывод в <tex>* \gamma_1'' и \gamma_2Gamma' =</tex>* \gamma_2''.

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

Данный вывод имеет вид (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>. Или вид (2): <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>, где <tex>q_1'</tex> {{---}} последовательность правил, которая осуществляет <tex>\gamma_1 \Rightarrow^* \gamma_1'</tex> и <tex>\gamma_2 \Rightarrow^* \gamma_2'</tex>, где <tex>q_2'</tex> {{---}} последовательность правил, осуществляющих <tex>\gamma_1' \Rightarrow^* \gamma_1''</tex> и <tex>DE\beta'\gamma_2' \Rightarrow^* \gamma_2''</tex>. Таким образом, существует вывод:<tex>S =>\Rightarrow^* \gamma_1AB\alpha'\gamma_2 => \Rightarrow \gamma_1CDE\beta'\gamma_2 => (\Rightarrow^{q_1) } \gamma_1'CDE\beta'\gamma_2' => (\Rightarrow^{q_2) } \gamma_1''DE\beta'\gamma_2'' =>\Rightarrow^* 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\Gamma) </tex> и <tex>L(G\Gamma') <= \subseteq L(G\Gamma)</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>.