Изменения

{{Определение|definition=[[Формальные грамматики|Грамматика ]] представлена в '''нормальной форме Куроды ''' (англ. ''Kuroda normal form''), если каждое правило имеет одну из четырех форм:# <tex>AB-\rightarrow CD</tex>CD# <tex>A-\rightarrow BC</tex>BC# <tex>A-\rightarrow B</tex>B# <tex>A-\rightarrow a</tex>a или <tex>A->\rightarrow \varepsilon</tex>Где <tex>A, B, C, D </tex> {{---}} нетерминалы, <tex>a </tex> {{---}} терминал.}}

Данная грамматика названа {{Определение|definition=Грамматика представлена в честь Куроды '''нормальной форме Пенттонена''' (англ. Sige''Penttonen normal form''), если каждое правило имеет одну из трех форм:# <tex>AB \rightarrow AC</tex># <tex>A \rightarrow BC</tex># <tex>A \rightarrow a</tex> или <tex>A \rightarrow \varepsilon</tex>Где <tex>A, B, C, D </tex> {{-Yuki Kuroda)--}} нетерминалы, который изначально назвал ее линейно ограниченной грамматикой<tex>a</tex> {{---}} терминал.}}

Грамматика представлена в Также грамматику Пенттонена называют односторонней нормальной форме Пенттонена формой (англ Penttonen . ''one-sided normal form''). Как можно заметить, если каждое правило имеет одну из трех формона является частным случаем нормальной формы Куроды:# AB-когда <tex>CD# A-= C</tex>BCв первом правиле определения.# AДля каждой контестно->a или A->\varepsilonГде A, B, C, D {{---}} нетерминалы, a {{---}} терминалзависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.

Также грамматику Пенттонена называют односторонней нормальной формой {{Лемма|about=об удалении терминалов|statement = Для любой грамматики <tex> \Gamma = \langle \Sigma, N, S, P \rangle</tex> может быть построена грамматика <tex>\Gamma' = \langle \Sigma, N', S, P' \rangle</tex> такая, что:* все правила в <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex> где <tex>\alpha \in (англ. one-sided normal formN')^+</tex> и <tex>\beta \in (N'). Как можно заметить^*</tex> или <tex>A \rightarrow a</tex>, она является частным случаем нормальной формы Куроды: когда где <tex>A \in N', a \in \Sigma</tex>,* <tex>L(\Gamma') = C в первом правиле определения.L(\Gamma)</tex>Для каждой контестноКроме того, если <tex>\Gamma</tex> контекстно-свободна или контекстно-зависима, то и <tex>\Gamma'</tex> будет соответственно контекстно-свободной или контекстно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.

Лемма 1. (Удаление терминалов)Для любой грамматики G |proof = (N, T, P, S) может быть построена грамматика G' = (NКаждому терминалу <tex>a</tex> поставим в соотвествие новый символ <tex>a'</tex>, T, P', S) такая, что:* все правила которого нет в P' имеет вид \alpha \rightarrow \beta где \alpha \in (<tex>N')^+ и \beta cup \in (NSigma</tex>, такой что <tex>a')^* или A \rightarrow a, где A \in Nneq b', </tex> для разных терминалов <tex>a \in T,* L(G') = L(G)Кроме того, если G контекстно-свободна или контекстно-зависима, то </tex> и G' будет соответственно контекстно-свободной или контекстно-зависимой<tex>b</tex>.

ДоказательствоПусть <tex>N' = N \cup \{a' \mid a \in \Sigma\}</tex>.

Каждому терминалу a поставим в соотвествие новый символ a', которого нет в N U T, такой что a' != b' для разных терминалов a и b.Пусть N' = N U \{a' | a \in T\}Пусть <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, если &;\ x_i \in N; \\x_i', если &;\ x_i \in T} для 1 <= i <= n.Построим грамматику G' = (N', T, P', S), где P' = {\alpha' Sigma\rightarrow \beta' : \alpha end{array}\rightarrow right.</tex> для <tex>1 \beta leqslant i \in P} U {a' \rightarrow a: a \in T}leqslant n</tex>.

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

Пусть w \in L(G). Тогда в G существует вывод S = w_0 => w_1 => ... => w_n => w. Согласно конструкции P'Покажем, в G' существует вывод S = w_0' => w_1' => w_2' => ... => w_n' = v_0 => v_1 => v_2 => ... => v_m = w.Для 0 что <= i <= n - 1 в переходах w_i' => w_{i + 1}' используем правило \alpha' \rightarrow \beta', так как правило \alpha \rightarrow \beta было использовано при выводе w_i => w_{i + 1}.Для 0 <= j <= m - 1 в переходах v_j =tex> v_{j + 1} используем правила вида a' \rightarrow a.Заменяем разрешенные в w' символы на новые и получаем, что w \in L(G\Gamma').Тогда = L(G\Gamma) <= L(G')/tex>.

Пусть <tex>w \in L(\Gamma)</tex>. Тогда в <tex>\Gamma</tex> существует вывод <tex>S = w_0 \Rightarrow w_1 \Rightarrow \ldots \Rightarrow w_n \Rightarrow w</tex>.  Согласно конструкции <tex>P'</tex>, в <tex>\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(\Gamma')</tex>.Тогда <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. Пусть <tex>x \in L(G\Gamma')</tex>. Тогда в G<tex>\Gamma' </tex> существует вывод <tex>S =>\Rightarrow^* x</tex>. Мы можем поменять порядок применения правил в этом выводе:сначала применяем только правила вида <tex>\alpha' \rightarrow \beta'</tex>, а потом только правила вида <tex>a' \rightarrow a</tex>.  Из построения: после применения правила вида <tex>a' \rightarrow a </tex> полученное <tex>a </tex> не может быть использовано при применении правил из <tex>P'</tex>.  Изменение порядка вывода не меняет язык, то есть в G<tex>\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<= s /tex> было использовано правило <tex>a' \rightarrow a</tex>, чтобы получить <tex>y_j \rightarrow y_{j + 1}</tex>. Получаем вывод в G<tex>\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>.

Лемма 2. Сначала докажем, что <tex>L(Удаление длинных правил\Gamma)Для любой грамматики G = \subseteq L(N, T, P, S) может быть построена грамматика G' = (N', T, P\Gamma', S) такая</tex>. Это следует из того, что:* любое правило все правила из P' имеет вид: <tex>P_1</tex> применимы к обеим грамматикам, * шаг вывода <tex>\gamma_1AB\alpha '\rightarrow gamma_2 \Rightarrow \gamma_1CDE\beta'\gamma_2</tex>, где благодаря правилу <tex>p = AB\alpha \rightarrow CDE\beta' \in (NP_2</tex> в <tex>\Gamma</tex>может быть использавано в <tex>\Gamma'</tex> с помощью трех шагов:<tex>\gamma_1AB\alpha')^+ и \beta gamma_2 \Rightarrow \gamma_1A_pB_p\in (Nalpha')^+ и |\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 a CDE\beta' \in P_3</tex> в <tex>G</tex>, которое может быть применено в <tex>G'</tex> с помощью трех шагов вывода: или A <tex>\gamma_1A\alpha1'\gamma_2 \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 \rightarrow Rightarrow \varepsilon, где A gamma_1CB_p\in Nalpha' и a \in Tgamma_2 \Rightarrow \gamma_1CDE\beta\gamma_2</tex>.* L(GТаким образом, любой вывод в <tex>\Gamma</tex> может быть преобразован в вывод в <tex>\Gamma') = L(G)</tex>.

Доказательство.Сначала по G построим грамматику G'' = Чтобы показать обратное включение, рассмотрим вывод <tex>w \in L(N\Gamma'', T, P'', S), как </tex> в доказательстве леммы 1. По G<tex>\Gamma'' построим грамматику G', в которой:N' = N'' U {D}</tex>, где D {{---}} новый символ,P' получаем из P'' заменой всех который содержит применение правил вида \alpha <tex>AB \rightarrow \beta \in P'', где |\alpha| A_pB_p</tex> |\beta| на для какого-то правила вида <tex>p = AB\alpha ' \rightarrow CDE\betaD^{|beta' \alpha| - |\beta|}in P_2</tex>. Заметим, и добавлением что другие два правила D из <tex>P_p</tex> могут быть применены только если правило <tex>AB \rightarrow \varepsilon.Теперь все правила A_pB_p</tex> было применено в P' имеет требуемую формуэтом выводе ранее.

Покажем, что LДанный вывод имеет вид (G'1) = L(G).Заметим, что замена правила \alpha \rightarrow \beta на \alpha \rightarrow \betaD^{|\alpha| - |\beta|} не меняет язык грамматики, потому что дополнительная буква D запрещается при добавлении перехода D \rightarrow \varepsilon, а других правил для D нет.Тогда получаем, что L(G) <= L(G'), аналогично обратные изменения не меняют язык, то есть L(G') <= L(G).:

Определение.Грамматика имеет порядок nгде <tex>q_2</tex> {{---}} последовательность правил, если |осуществляющих <tex>\alpha| gamma_1'C \Rightarrow^* \gamma_1''<= n /tex> и |\beta| <= n для любого ее правила tex>\alpha gamma_2' \rightarrow Rightarrow^* \betagamma_2''</tex>.

Лемма 3. (Уменьшение порядка грамматики)Для любой грамматики G = (N, T, P, <tex>S) порядка n >= 3, такой что: любое правило из P\Rightarrow^* \gamma_1AB\alpha' имеет вид \gamma_2 \Rightarrow \gamma_1A_pB_p\alpha '\gamma_2 \rightarrow Rightarrow^{q_1'} \beta, где gamma_1' A_p B_p \alpha ' \in (Ngamma_2' \Rightarrow \gamma_1')^+ и A_pDE\beta '\in (Nalpha')^+ и |\alpha| <= |gamma_2' \beta| или A Rightarrow^{q_2'} \rightarrow a или A gamma_1''A_p\rightarrow gamma_2'' \varepsilon, где A Rightarrow \in Ngamma_1'' и a C\in T может быть построена грамматика Ggamma_2' = (N', \Rightarrow^* w \in T^*</tex>, P', S) порядка n - 1 такая, что L(G') = L(G).

Доказательство.Разделим P на три подмножества:P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| где <= 2, |\beta| tex>q_1'<= 2 \/tex> {{---}}последовательность правил,P_2 = \{ которая осуществляет <tex>\alpha gamma_1 \rightarrow Rightarrow^* \beta | \alpha \rightarrow \beta \in P, |\alpha| gamma_1'</tex>= 2, |\beta| и <tex>= 3 \},P_3 = gamma_2 \{ Rightarrow^* \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| gamma_2'</tex>= 3 \}.Очевидно, что P = P_1 U P_2 U P_3.

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

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

Покажем, что Тогда <tex>w \in L(G\Gamma)</tex> и <tex>L(\Gamma') = \subseteq L(G\Gamma)</tex>.}}

Сначала докажем{{Теорема|statement=Любую грамматику <tex>\Gamma</tex> можно преобразовать к грамматике <tex>\Gamma_K</tex> в нормальной форме Куроды так, что <tex>L(G\Gamma) <= L(G'\Gamma_K)</tex>. Это следует из того, что:* все правила |proof=По лемме 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 =Gamma</tex> \gamma_1A_pB_p\alpha'\gamma_2 =грамматику <tex> \gamma_1CB_p\alphaGamma'\gamma_2 =</tex> \gamma_1CDE\beta\gamma_2, с использованием правил затем по лемме 2 построим из P_p и вывода <tex>\gamma_1A\gamma_2 =Gamma'</tex> грамматику <tex> \gamma_1CDE\betaGamma'\gamma_2 на основе правила p = A\alpha \rightarrow CDE\beta' \in P_3 в G</tex>, которое может быть применено в G' с помощью трех шагов вывода:\gamma_1A\alpha1'\gamma_2 =Тогда <tex> \gamma_1A_pB_p\alphaGamma'\gamma_2 => \gamma_1CB_p\alpha'\gamma_2 =</tex> \gamma_1CDE\beta\gamma_2.Таким образом, любой вывод в G может быть преобразован в вывод в G'удовлетворит требованиям леммы 3.

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

Или (2) 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^*,где q_1' {{---}} последовательность правил, которая осуществляет \gamma_1 =>* \gamma_1' и \gamma_2 =>* \gamma_2',[[Нормальная_форма_Хомского|Нормальная форма Хомского]]где q_2' {{---}} последовательность правил, осуществляющих \gamma_1' =>* \gamma_1'' и DE\beta'\gamma_2' =>* \gamma_2''.[[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах|Приведение грамматики к ослабленной нормальной форме Грейбах]]

Таким образом, существует вывод: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^Alexander Meduna Automata and Languages: Theory and Applications*,который получается из (1) заменой правил P_p на применение p = AB\alpha' \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 L(G) и L(G') <= L(G).[[wikipedia:Kuroda_normal_form | Wikipedia {{---}} Kuroda normal form]]

Теорема.Любую грамматику G можно преобразовать к грамматике G_K в нормальной форме Куроды, так что L(G) = L(G_K).Доказательство.По лемме 1 построим из G грамматику G', затем по лемме 2 построим из G' грамматику G'', Тогда G'' удовлетворит требованиям леммы 3.Пусть G'' имеет порядок n. Нсли n = 2, то G'' в нормальной форме Куроды и G_K = G''. Если n >= 3, построим G''' порядка n [[Категория: Теория формальных языков]] [[Категория: Контекстно- 1 из G'' по лемме 3.Понятно, что G''' удовлетворяет условиям леммы 3, будем повторять процесс, пока не получим грамматику порядка 2, которую и примем за G_K.свободные грамматики ]] [[Категория: Нормальные формы КС-грамматик ]]