Изменения

Перейти к: навигация, поиск

Нормальная форма Куроды

4506 байт добавлено, 19:29, 4 сентября 2022
м
rollbackEdits.php mass rollback
{{Определение
|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> {{---}} терминал.
}}
 
Данная грамматика названа в честь Куроды (англ. Sige-Yuki Kuroda), который изначально назвал ее линейно ограниченной грамматикой.
{{Определение
|definition=Грамматика представлена в '''нормальной форме Пенттонена''' (англ. ''Penttonen normal form''), если каждое правило имеет одну из трех форм:
# <tex>AB-\rightarrow AC</tex>CD# <tex>A-\rightarrow BC</tex>BC# <tex>A-\rightarrow a</tex>a или <tex>A->\rightarrow \varepsilon</tex>Где <tex>A, B, C, D </tex> {{---}} нетерминалы, <tex>a </tex> {{---}} терминал.
}}
Также грамматику Пенттонена называют односторонней нормальной формой (англ. ''one-sided normal form''). Как можно заметить, она является частным случаем нормальной формы Куроды: когда <tex>A = C </tex> в первом правиле определения.Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.
{{Лемма
|about=об удалении терминалов
|statement = Для любой грамматики G <tex> \Gamma = (\langle \Sigma, N, TS, P, S) \rangle</tex> может быть построена грамматика G<tex>\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> контекстно-свободна или контекстно-зависима, то и G<tex>\Gamma' </tex> будет соответственно контекстно-свободной или контекстно-зависимой. |proof = Каждому терминалу <tex>a</tex> поставим в соотвествие новый символ <tex>a'</tex>, которого нет в <tex>N \cup \Sigma</tex>, такой что <tex>a' \neq b'</tex> для разных терминалов <tex>a</tex> и <tex>b</tex>. Пусть <tex>N' = N \cup \{a' \mid a \in \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&;\ x_i \in N\\x_i'&;\ x_i \in \Sigma\\\end{array}\right.</tex> для <tex>1 \leqslant i \leqslant n</tex>. Построим грамматику <tex>G' = \langle \Sigma, N', S, P' \rangle</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' \mid \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a \mid a \in \Sigma\}</tex>. Покажем, что <tex>L(\Gamma') = L(\Gamma)</tex>.
|proof = Каждому терминалу a поставим в соотвествие новый символ a', которого нет в N U T, такой что a' != b' для разных терминалов a и b.Пусть N' = N U \{a' | a <tex>w \in TL(\}Пусть \alpha = x_1x_2Gamma)</tex>...x_n {{---}} часть правила, тогда \alpha' = y_1y_2...y_n, где y_i = {x_i, если x_i \in N; x_i', если x_i Тогда в <tex>\in T} для 1 Gamma<= i /tex> существует вывод <= n.Построим грамматику G' = (N', T, P', tex>S), где P' = {w_0 \alpha' Rightarrow w_1 \rightarrow Rightarrow \beta' : ldots \alpha Rightarrow w_n \rightarrow \beta \in P} U {a' \rightarrow a: a \in T}Rightarrow w</tex>.
ПокажемСогласно конструкции <tex>P'</tex>, что L(Gв <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 = L(G)w</tex>.
Пусть w \in L(G). Тогда в G существует вывод S = w_0 => w_1 => ... => w_n => w. Согласно конструкции P', в G' существует вывод S = w_0' =Для <tex> w_1' => w_2' => ... => w_n' = v_0 => v_1 => v_2 => ... => v_m = w.Для 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}.Для 0 <= j <= m - 1 в переходах v_j =/tex> v_{j + 1} используем правила вида a' \rightarrow a.Заменяем разрешенные в w' символы на новые и получаем, что w \in L(G').Тогда L(G) <= L(G').
Для <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>.
Очевидно, что если грамматика была неукорочивающейся, то она такой и останется.
}}
{{Лемма
|about=об удалении длинных коротких правил|statement= Для любой грамматики G <tex>\Gamma = (\langle \Sigma, N, TS, P, S) \rangle</tex> может быть построена грамматика G<tex>\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>
|proof=
Сначала по G <tex>\Gamma</tex> построим грамматику G<tex>\Gamma'' = (\langle \Sigma, N'', TS, P'', S)\rangle</tex>, как в доказательстве леммы 1. По G<tex>\Gamma'' </tex> построим грамматику G<tex>\Gamma'</tex>, в которой:* <tex>N' = N'' U \cup \{D\}</tex>, где <tex>D </tex> {{---}} новый символ,* <tex>P' </tex> получаем из <tex>P'' </tex> заменой всех правил вида <tex>\alpha \rightarrow \beta \in P''</tex>, где <tex>|\alpha| > |\beta| </tex> на правила вида <tex>\alpha \rightarrow \betaDbeta D^{|\alpha| - |\beta|}</tex>, и добавлением правила <tex>D \rightarrow \varepsilon.Теперь все правила в P' имеет требуемую форму</tex>.
Теперь все правила в <tex>P'</tex> имеет требуемую форму.  Покажем, что <tex>L(G\Gamma') = L(G\Gamma)</tex>. Заметим, что замена правила <tex>\alpha \rightarrow \beta </tex> на <tex>\alpha \rightarrow \betaDbeta D^{|\alpha| - |\beta|} </tex> не меняет язык грамматики, потому что дополнительная буква <tex>D запрещается при добавлении перехода D \rightarrow </tex> переходит только в <tex>\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>.
}}
{{Лемма
|about=об уменьшении порядка грамматики
|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| <= 2, |\beta| <= leqslant 2 \},P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| >= leqslant 2, |\beta| >= 3 \},P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| </tex>= 3 \}.Очевидно, что P = P_1 U P_2 U P_3.
Построим G' следующим образом:* Если правило p <tex>P_2 = \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_pmid \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_3P, то оно имеет вид A |\rightarrow CDEalpha| \beta'geqslant 2, где |\beta' \int N^*. Полагаем N_p = \{B_p | \}, P_p = \{A \rightarrow CB_p, B_p \rightarrow DE\beta'geqslant 3 \}</tex>, где A_p, B_p {{---}} дополнительные символы.
Тогда N' <tex>P_3 = N U (объединение по \{ \alpha \rightarrow \beta \mid \alpha \rightarrow \beta \in P из (P_2 U P_3) N_p), P' |\alpha| = P_1 U (объединение по P из (P_2 U P_3) P_p).Из построения очевидно1, что G' имеет порядок n - 1|\beta| \geqslant 3 \}</tex>.
ПокажемОчевидно, что L(G') <tex>P = L(G)P_1 \cup P_2 \cup P_3</tex>.
Сначала докажем, что L(G) Построим <= L(Gtex>\Gamma'). Это следует из того, что</tex> следующим образом:* все правила из P_1 применимы к обеим грамматикам, * шаг вывода Если правило <tex>p \gamma_1AB\alpha'\gamma_2 =in P_2</tex> \gamma_1CDE\beta'\gamma_2, благодаря правилу p = то оно имеет вид <tex>AB\alpha ' \rightarrow CDE\beta' \in P_2 в G</tex>, может быть использавано в G' с помощью трех шагов:\gamma_1AB\alpha'\gamma_2 =где <tex> \gamma_1A_pB_p\alpha'\gamma_2 => \gamma_1CB_p\alpha'\gamma_2 =in N^*</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'\gamma_2 =N^*</tex> \gamma_1A_pB_p\alpha'\gamma_2 => \gamma_1CB_p\alpha'\gamma_2 => \gamma_1CDE\beta\gamma_2.Таким образом, любой вывод в G может быть преобразован в вывод в G'.
Чтобы показать обратное включениеПолагаем <tex>N_p = \{ A_p, рассмотрим вывод w B_p \in L(G') в G'}</tex>, который содержит применение правил вида <tex>P_p = \{ AB \rightarrow A_pB_p для какого-то правила p = AB\alpha' , A_p \rightarrow CDE\beta' \in P_2 (ЗаметимC, что другие два правила из 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' =>(q_2) \gamma_1''B_p\alpha'\gamma_2'' => \gamma_1''rightarrow DE\beta'\gamma_2'' =}</tex>* w \in T^*,где q_1 <tex>A_p, B_p</tex> {{---}} последовательность правил, примененых после AB дополнительные символы не из <tex>N: \rightarrow A_pB_p и до {A_p \rightarrow C, которая осуществляет B_p\gamma_1 =>* } \gamma_1' и \gamma_2 =>* cap \gamma_2',где q_2 {{---}} последовательность правилA_q, осуществляющих B_q\gamma_1'C } =0</tex> для разных правил <tex>p</tex>* \gamma_1'' и \gamma_2' =<tex>q</tex> из <tex>P_2</tex>* \gamma_2''.
Или (2) S =>* \gamma_1AB\alpha'\gamma_2 =Если правило <tex> p \gamma_1A_pB_p\alpha'\gamma_2 =in P_3</tex>(q_1') \gamma_1'A_pB_p\alpha'\gamma_2' =, то оно имеет вид <tex> A \gamma_1'A_pDErightarrow CDE\beta'\alpha'\gamma_2' =</tex>(q_2') \gamma_1''A_p\gamma_2'' =, где <tex> \gamma_1''C\gamma_2'beta' =>* w \in TN^*,где q_1' {{---}} последовательность правил, которая осуществляет \gamma_1 =>* \gamma_1' и \gamma_2 =>* \gamma_2',где q_2' {{---}} последовательность правил, осуществляющих \gamma_1' =>* \gamma_1'' и DE\beta'\gamma_2' =</tex>* \gamma_2''.
Таким образомПолагаем <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 \bigcup\limits_{p \in (P_2 \cup P_3)} N_p</tex>, <tex>P' = P_1 \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>. Это следует из того, существует выводчто:S =* все правила из <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>. Или вид (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'CDEA_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>.
}}
{{Теорема
|statement=
Любую грамматику G <tex>\Gamma</tex> можно преобразовать к грамматике G_K <tex>\Gamma_K</tex> в нормальной форме Куродытак, так что <tex>L(G\Gamma) = L(G_K\Gamma_K)</tex>.
|proof=
По лемме 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>.
}}
 
== См. также ==
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах|Приведение грамматики к ослабленной нормальной форме Грейбах]]
 
== Источники информации ==
* Alexander Meduna Automata and Languages: Theory and Applications
* [[wikipedia:Kuroda_normal_form | Wikipedia {{---}} Kuroda normal form]]
 
[[Категория: Теория формальных языков]] [[Категория: Контекстно-свободные грамматики ]] [[Категория: Нормальные формы КС-грамматик ]]
1632
правки

Навигация