Нормальная форма Куроды — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 25 промежуточных версий 5 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition=Грамматика представлена в '''нормальной форме Куроды''' (англ.  ''Kuroda normal form''), если каждое правило имеет одну из четырех форм:
+
|definition=[[Формальные грамматики|Грамматика]] представлена в '''нормальной форме Куроды''' (англ.  ''Kuroda normal form''), если каждое правило имеет одну из четырех форм:
 
# <tex>AB \rightarrow CD</tex>
 
# <tex>AB \rightarrow CD</tex>
 
# <tex>A \rightarrow BC</tex>
 
# <tex>A \rightarrow BC</tex>
Строка 7: Строка 7:
 
Где <tex>A, B, C, D</tex> {{---}} нетерминалы, <tex>a</tex> {{---}} терминал.
 
Где <tex>A, B, C, D</tex> {{---}} нетерминалы, <tex>a</tex> {{---}} терминал.
 
}}
 
}}
 
Данная грамматика названа в честь Куроды (англ. Sige-Yuki Kuroda), который изначально назвал ее линейно ограниченной грамматикой.
 
  
 
{{Определение
 
{{Определение
 
|definition=Грамматика представлена в '''нормальной форме Пенттонена''' (англ. ''Penttonen normal form''), если каждое правило имеет одну из трех форм:
 
|definition=Грамматика представлена в '''нормальной форме Пенттонена''' (англ. ''Penttonen normal form''), если каждое правило имеет одну из трех форм:
# <tex>AB \rightarrow CD</tex>
+
# <tex>AB \rightarrow AC</tex>
 
# <tex>A \rightarrow BC</tex>
 
# <tex>A \rightarrow BC</tex>
 
# <tex>A \rightarrow a</tex> или <tex>A \rightarrow \varepsilon</tex>
 
# <tex>A \rightarrow a</tex> или <tex>A \rightarrow \varepsilon</tex>
Строка 19: Строка 17:
  
 
Также грамматику Пенттонена называют односторонней нормальной формой (англ. ''one-sided normal form''). Как можно заметить, она является частным случаем нормальной формы Куроды: когда <tex>A = C</tex> в первом правиле определения.
 
Также грамматику Пенттонена называют односторонней нормальной формой (англ. ''one-sided normal form''). Как можно заметить, она является частным случаем нормальной формы Куроды: когда <tex>A = C</tex> в первом правиле определения.
Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.  
+
Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.
  
 
{{Лемма
 
{{Лемма
 
|about=об удалении терминалов
 
|about=об удалении терминалов
|statement = Для любой грамматики <tex>G = (N, T, P, S)</tex> может быть построена грамматика <tex>G' = (N', T, P', S)</tex> такая, что:
+
|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 (N')^+</tex> и <tex>\beta \in (N')^*</tex> или <tex>A \rightarrow a</tex>, где <tex>A \in N', a \in T</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 \Sigma</tex>,
* <tex>L(G') = L(G)</tex>
+
* <tex>L(\Gamma') = L(\Gamma)</tex>
Кроме того, если G контекстно-свободна или контекстно-зависима, то и <tex>G'</tex> будет соответственно контекстно-свободной или контекстно-зависимой.
+
Кроме того, если <tex>\Gamma</tex> контекстно-свободна или контекстно-зависима, то и <tex>\Gamma'</tex> будет соответственно контекстно-свободной или контекстно-зависимой.
  
|proof = Каждому терминалу <tex>a</tex> поставим в соотвествие новый символ <tex>a'</tex>, которого нет в <tex>N \cup T</tex>, такой что <tex>a' \neq b'</tex> для разных терминалов <tex>a</tex> и <tex>b</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' | a \in T\}</tex>.
+
Пусть <tex>N' = N \cup \{a' \mid a \in \Sigma\}</tex>.
  
Пусть <tex>\alpha = x_1x_2...x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2...y_n</tex>, где <tex>y_i = \{x_i</tex>, если <tex>x_i \in N</tex>; <tex>x_i'</tex>, если <tex>x_i \in T\}</tex> для <tex>1 <= i <= n</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' = (N', T, P', S)</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: a \in T\}</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(G') = L(G)</tex>.
+
Покажем, что <tex>L(\Gamma') = L(\Gamma)</tex>.
  
Пусть <tex>w \in L(G)</tex>. Тогда в G существует вывод <tex>S = w_0 => w_1 => ... => w_n => w</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>G'</tex> существует вывод <tex>S = w_0' => w_1' => w_2' => ... => w_n' = v_0 => v_1 => v_2 => ... => v_m = 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 <= i <= n - 1</tex> в переходах <tex>w_i' => w_{i + 1}'</tex> используем правило <tex>\alpha' \rightarrow \beta'</tex>, так как правило <tex>\alpha \rightarrow \beta</tex> было использовано при выводе <tex>w_i => w_{i + 1}</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 <= j <= m - 1</tex> в переходах <tex>v_j => v_{j + 1}</tex> используем правила вида <tex>a' \rightarrow a</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')</tex>.
+
Заменяем разрешенные в <tex>w'</tex> символы на новые и получаем, что <tex>w \in L(\Gamma')</tex>.
Тогда <tex>L(G) <= L(G')</tex>.
+
Тогда <tex>L(\Gamma) \subseteq L(\Gamma')</tex>.
  
Пусть <tex>x \in L(G')</tex>. Тогда в <tex>G'</tex> существует вывод <tex>S =>* x</tex>. Мы можем поменять порядок применения правил в этом выводе: сначала применяем только правила вида <tex>\alpha' \rightarrow \beta'</tex>, а потом только правила вида <tex>a' \rightarrow a</tex>.  
+
Пусть <tex>x \in L(\Gamma')</tex>. Тогда в <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>.  
 
Из построения: после применения правила вида <tex>a' \rightarrow a</tex> полученное <tex>a</tex> не может быть использовано при применении правил из <tex>P'</tex>.  
  
Изменение порядка вывода не меняет язык, то есть в <tex>G'</tex> существует вывод: <tex>S = x_0' => x_1' => ... => x_r' => x' => y_1 => y_2 => ... => y_s = x</tex>, где для <tex>0 <= i <= r - 1 x_{i + 1}' \in (N')^*</tex> и в переходе <tex>x_i' \rightarrow x_{i + 1}'</tex> было использовано правило вывода <tex>\alpha' \rightarrow \beta'</tex> и для <tex>1 <= j <= s</tex> было использовано правило <tex>a' \rightarrow a</tex>, чтобы получить <tex>y_j \rightarrow y_{j + 1}</tex>.
+
Изменение порядка вывода не меняет язык, то есть в <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</tex> было использовано правило <tex>a' \rightarrow a</tex>, чтобы получить <tex>y_j \rightarrow y_{j + 1}</tex>.
 +
 
 +
Получаем вывод в <tex>\Gamma</tex>: <tex>S = x_0 \Rightarrow x_1 \Rightarrow \ldots \Rightarrow x_n = x</tex>.
  
Получаем вывод в <tex>G</tex>: <tex>S = x_0 => x_1 => ... => x_n = x</tex>.
+
Тогда <tex>L(\Gamma') \subseteq L(\Gamma)</tex>.
Тогда <tex>L(G') <= L(G)</tex>.
+
 
Таким образом, <tex>L(G') = L(G)</tex>.
+
Таким образом, <tex>L(\Gamma') = L(\Gamma)</tex>.
 
Очевидно, что если грамматика была неукорочивающейся, то она такой и останется.
 
Очевидно, что если грамматика была неукорочивающейся, то она такой и останется.
 
}}
 
}}
  
 
{{Лемма
 
{{Лемма
|about=об удалении длинных правил
+
|about=об удалении коротких правил
|statement= Для любой грамматики <tex>G = (N, T, P, S)</tex> может быть построена грамматика  <tex>G' = (N', T, P', S)</tex> такая, что:
+
|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 (N')^+</tex> и <tex>\beta \in (N')^+</tex> и <tex>|\alpha| <= |\beta|</tex>, или <tex>A \rightarrow a</tex>, или <tex>A \rightarrow \varepsilon</tex>, где <tex>A \in N'</tex> и <tex>a \in T</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') = L(G)</tex>
+
* <tex>L(\Gamma') = L(\Gamma)</tex>
 
|proof=
 
|proof=
Сначала по G построим грамматику G'' = (N'', T, P'', S), как в доказательстве леммы 1. По G'' построим грамматику G', в которой:
+
Сначала по <tex>\Gamma</tex> построим грамматику <tex>\Gamma'' = \langle \Sigma, N'', S, P'' \rangle</tex>, как в доказательстве леммы 1. По <tex>\Gamma''</tex> построим грамматику <tex>\Gamma'</tex>, в которой:
N' = N'' U {D}, где D {{---}} новый символ,
+
* <tex>N' = N'' \cup \{D\}</tex>, где <tex>D</tex> {{---}} новый символ,
P' получаем из P'' заменой всех правил вида \alpha \rightarrow \beta \in P'', где |\alpha| > |\beta| на правила вида \alpha \rightarrow \betaD^{|\alpha| - |\beta|}, и добавлением правила D \rightarrow \varepsilon.
+
* <tex>P'</tex> получаем из <tex>P''</tex> заменой всех правил вида <tex>\alpha \rightarrow \beta \in P''</tex>, где <tex>|\alpha| > |\beta|</tex> на правила вида <tex>\alpha \rightarrow \beta D^{|\alpha| - |\beta|}</tex>, и добавлением правила <tex>D \rightarrow \varepsilon</tex>.
Теперь все правила в P' имеет требуемую форму.  
+
 
 +
Теперь все правила в <tex>P'</tex> имеет требуемую форму.
 +
 
 +
Покажем, что <tex>L(\Gamma') = L(\Gamma)</tex>.
 +
 
 +
Заметим, что замена правила <tex>\alpha \rightarrow \beta</tex> на <tex>\alpha \rightarrow \beta D^{|\alpha| - |\beta|}</tex> не меняет язык грамматики, потому что <tex>D</tex> переходит только в <tex>\varepsilon</tex>, а других правил для <tex>D</tex> нет.
  
Покажем, что L(G') = L(G).
+
Тогда получаем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>, аналогично обратные изменения не меняют язык, то есть <tex>L(\Gamma') \subseteq L(\Gamma)</tex>.
Заметим, что замена правила \alpha \rightarrow \beta на \alpha \rightarrow \betaD^{|\alpha| - |\beta|} не меняет язык грамматики, потому что дополнительная буква D запрещается при добавлении перехода D \rightarrow \varepsilon, а других правил для D нет.
 
Тогда получаем, что L(G) <= L(G'), аналогично обратные изменения не меняют язык, то есть L(G') <= L(G).
 
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition=Грамматика имеет '''порядок n''', если |\alpha| <= n и |\beta| <= n для любого ее правила \alpha \rightarrow \beta.
+
|definition=Грамматика имеет '''порядок <tex>n</tex>''', если <tex>|\alpha| \leqslant n</tex> и <tex>|\beta| \leqslant n</tex> для любого ее правила <tex>\alpha \rightarrow \beta</tex>.
 
}}
 
}}
  
Строка 84: Строка 93:
 
{{Лемма
 
{{Лемма
 
|about=об уменьшении порядка грамматики
 
|about=об уменьшении порядка грамматики
|statement=(Уменьшение порядка грамматики)
+
|statement=
Для любой грамматики G = (N, T, P, S) порядка n >= 3, такой что: любое правило из P' имеет вид \alpha \rightarrow \beta, где \alpha \in (N')^+ и \beta \in (N')^+ и |\alpha| <= |\beta| или A \rightarrow a или A \rightarrow \varepsilon, где A \in N' и a \in T  
+
Для любой грамматики <tex>\Gamma = \langle \Sigma, N, S, P \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>\Gamma' = \langle \Sigma, N', S, P' \rangle</tex> порядка <tex>n - 1</tex> такая, что <tex>L(\Gamma') = L(\Gamma)</tex>.
может быть построена грамматика  G' = (N', T, P', S) порядка n - 1 такая, что L(G') = L(G).
+
|proof=  
|proof= Разделим P на три подмножества:
+
Разделим <tex>P</tex> на три подмножества:
P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| <= 2, |\beta| <= 2 \},
+
 
P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| >= 2, |\beta| >= 3 \},
+
<tex>P_1 = \{ \alpha \rightarrow \beta \mid \alpha \rightarrow \beta \in P, |\alpha| \leqslant 2, |\beta| \leqslant 2 \}</tex>,
P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| >= 3 \}.
+
 
Очевидно, что P = P_1 U P_2 U P_3.
+
<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 \cup P_2 \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>.
 +
 
 +
Полагаем <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>. Это следует из того, что:
 +
* все правила из <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>,
  
Построим G' следующим образом:
+
где <tex>q_2</tex> {{---}} последовательность правил, осуществляющих <tex>\gamma_1'C \Rightarrow^* \gamma_1''</tex> и <tex>\gamma_2' \Rightarrow^* \gamma_2''</tex>.
* Если правило 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^*.
 
Полагаем N_p = \{B_p \}, P_p = \{A \rightarrow CB_p, B_p \rightarrow DE\beta'\}, где A_p, B_p {{---}} дополнительные символы.
 
  
Тогда N' = N U (объединение по P из (P_2 U P_3) N_p), P' = P_1 U (объединение по P из (P_2 U P_3) P_p).
+
Или вид (2):
Из построения очевидно, что G' имеет порядок n - 1.
 
  
Покажем, что L(G') = L(G).
+
<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'). Это следует из того, что:
+
где <tex>q_1'</tex> {{---}} последовательность правил, которая осуществляет <tex>\gamma_1 \Rightarrow^* \gamma_1'</tex> и <tex>\gamma_2 \Rightarrow^* \gamma_2'</tex>,
* все правила из 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 => \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 \in L(G') в G', который содержит применение правил вида AB \rightarrow A_pB_p для какого-то правила p = AB\alpha' \rightarrow CDE\beta' \in P_2
+
где <tex>q_2'</tex> {{---}} последовательность правил, осуществляющих <tex>\gamma_1' \Rightarrow^* \gamma_1''</tex> и <tex>DE\beta'\gamma_2' \Rightarrow^* \gamma_2''</tex>.
(Заметим, что другие два правила из 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''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''.
 
  
Или (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^*,
+
Таким образом, существует вывод: <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>.
где q_1' {{---}} последовательность правил, которая осуществляет \gamma_1 =>* \gamma_1' и \gamma_2 =>* \gamma_2',
+
где q_2' {{---}} последовательность правил, осуществляющих \gamma_1' =>* \gamma_1'' и DE\beta'\gamma_2' =>* \gamma_2''.
+
Таким образом, для <tex>r \in P_2 \cup P_3</tex> мы можем заменить все применения <tex>P_r</tex> на <tex>r</tex>, то есть получаем вывод <tex>w</tex>, который состоит только из правил из <tex>P</tex>.  
  
Таким образом, существует вывод:
+
Тогда <tex>w \in L(\Gamma)</tex> и <tex>L(\Gamma') \subseteq L(\Gamma)</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^*,
 
который получается из (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).
 
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Любую грамматику G можно преобразовать к грамматике G_K в нормальной форме Куроды, так что L(G) = L(G_K).
+
Любую грамматику <tex>\Gamma</tex> можно преобразовать к грамматике <tex>\Gamma_K</tex> в нормальной форме Куроды так, что <tex>L(\Gamma) = L(\Gamma_K)</tex>.
 
|proof=
 
|proof=
По лемме 1 построим из G грамматику G', затем по лемме 2 построим из G' грамматику G'', Тогда G'' удовлетворит требованиям леммы 3.
+
По лемме 1 построим из <tex>\Gamma</tex> грамматику <tex>\Gamma'</tex>, затем по лемме 2 построим из <tex>\Gamma'</tex> грамматику <tex>\Gamma''</tex>, Тогда <tex>\Gamma''</tex> удовлетворит требованиям леммы 3.
Пусть G'' имеет порядок n. Нсли n = 2, то G'' в нормальной форме Куроды и G_K = G''. Если n >= 3, построим G''' порядка n - 1 из G'' по лемме 3.
+
 
Понятно, что G''' удовлетворяет условиям леммы 3, будем повторять процесс, пока не получим грамматику порядка 2, которую и примем за G_K.
+
Пусть <tex>\Gamma''</tex> имеет порядок <tex>n</tex>.  
 +
Если <tex>n = 2</tex>, то <tex>\Gamma''</tex> в нормальной форме Куроды и <tex>\Gamma_K = \Gamma''</tex>.  
 +
Если <tex>n \geqslant 3</tex>, построим <tex>\Gamma'''</tex> порядка <tex>n - 1</tex> из <tex>\Gamma''</tex> по лемме 3.
 +
Понятно, что <tex>\Gamma'''</tex> удовлетворяет условиям леммы 3.
 +
Будем повторять процесс, пока не получим грамматику порядка <tex>2</tex>, которую и примем за <tex>\Gamma_K</tex>.
 
}}
 
}}
 +
 +
== См. также ==
 +
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
 +
* [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах|Приведение грамматики к ослабленной нормальной форме Грейбах]]
 +
 +
== Источники информации ==
 +
* Alexander Meduna Automata and Languages: Theory and Applications
 +
* [[wikipedia:Kuroda_normal_form | Wikipedia {{---}} Kuroda normal form]]
 +
 +
[[Категория: Теория формальных языков]] [[Категория: Контекстно-свободные грамматики ]] [[Категория: Нормальные формы КС-грамматик ]]

Текущая версия на 19:29, 4 сентября 2022

Определение:
Грамматика представлена в нормальной форме Куроды (англ. Kuroda normal form), если каждое правило имеет одну из четырех форм:
  1. [math]AB \rightarrow CD[/math]
  2. [math]A \rightarrow BC[/math]
  3. [math]A \rightarrow B[/math]
  4. [math]A \rightarrow a[/math] или [math]A \rightarrow \varepsilon[/math]
Где [math]A, B, C, D[/math] — нетерминалы, [math]a[/math] — терминал.


Определение:
Грамматика представлена в нормальной форме Пенттонена (англ. Penttonen normal form), если каждое правило имеет одну из трех форм:
  1. [math]AB \rightarrow AC[/math]
  2. [math]A \rightarrow BC[/math]
  3. [math]A \rightarrow a[/math] или [math]A \rightarrow \varepsilon[/math]
Где [math]A, B, C, D [/math] — нетерминалы, [math]a[/math] — терминал.


Также грамматику Пенттонена называют односторонней нормальной формой (англ. one-sided normal form). Как можно заметить, она является частным случаем нормальной формы Куроды: когда [math]A = C[/math] в первом правиле определения. Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.

Лемма (об удалении терминалов):
Для любой грамматики [math] \Gamma = \langle \Sigma, N, S, P \rangle[/math] может быть построена грамматика [math]\Gamma' = \langle \Sigma, N', S, P' \rangle[/math] такая, что:
  • все правила в [math]P'[/math] имеет вид [math]\alpha \rightarrow \beta[/math] где [math]\alpha \in (N')^+[/math] и [math]\beta \in (N')^*[/math] или [math]A \rightarrow a[/math], где [math]A \in N', a \in \Sigma[/math],
  • [math]L(\Gamma') = L(\Gamma)[/math]
Кроме того, если [math]\Gamma[/math] контекстно-свободна или контекстно-зависима, то и [math]\Gamma'[/math] будет соответственно контекстно-свободной или контекстно-зависимой.
Доказательство:
[math]\triangleright[/math]

Каждому терминалу [math]a[/math] поставим в соотвествие новый символ [math]a'[/math], которого нет в [math]N \cup \Sigma[/math], такой что [math]a' \neq b'[/math] для разных терминалов [math]a[/math] и [math]b[/math].

Пусть [math]N' = N \cup \{a' \mid a \in \Sigma\}[/math].

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

Построим грамматику [math]G' = \langle \Sigma, N', S, P' \rangle[/math], где [math]P' = \{\alpha' \rightarrow \beta' \mid \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a \mid a \in \Sigma\}[/math].

Покажем, что [math]L(\Gamma') = L(\Gamma)[/math].

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

Согласно конструкции [math]P'[/math], в [math]\Gamma'[/math] существует вывод [math]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[/math].

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

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

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

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

Из построения: после применения правила вида [math]a' \rightarrow a[/math] полученное [math]a[/math] не может быть использовано при применении правил из [math]P'[/math].

Изменение порядка вывода не меняет язык, то есть в [math]\Gamma'[/math] существует вывод: [math]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[/math], где для [math]0 \leqslant i \leqslant r - 1 \ x_{i + 1}' \in (N')^*[/math] и в переходе [math]x_i' \rightarrow x_{i + 1}'[/math] было использовано правило вывода [math]\alpha' \rightarrow \beta'[/math] и для [math]1 \leqslant j \leqslant s[/math] было использовано правило [math]a' \rightarrow a[/math], чтобы получить [math]y_j \rightarrow y_{j + 1}[/math].

Получаем вывод в [math]\Gamma[/math]: [math]S = x_0 \Rightarrow x_1 \Rightarrow \ldots \Rightarrow x_n = x[/math].

Тогда [math]L(\Gamma') \subseteq L(\Gamma)[/math].

Таким образом, [math]L(\Gamma') = L(\Gamma)[/math].

Очевидно, что если грамматика была неукорочивающейся, то она такой и останется.
[math]\triangleleft[/math]
Лемма (об удалении коротких правил):
Для любой грамматики [math]\Gamma = \langle \Sigma, N, S, P \rangle[/math] может быть построена грамматика [math]\Gamma' = \langle \Sigma, N', S, P' \rangle[/math] такая, что:
  • любое правило из [math]P'[/math] имеет вид: [math]\alpha \rightarrow \beta[/math], где [math]\alpha \in (N')^+[/math] и [math]\beta \in (N')^+[/math] и [math]|\alpha| \leqslant |\beta|[/math], или [math]A \rightarrow a[/math], или [math]A \rightarrow \varepsilon[/math], где [math]A \in N'[/math] и [math]a \in T[/math]
  • [math]L(\Gamma') = L(\Gamma)[/math]
Доказательство:
[math]\triangleright[/math]

Сначала по [math]\Gamma[/math] построим грамматику [math]\Gamma'' = \langle \Sigma, N'', S, P'' \rangle[/math], как в доказательстве леммы 1. По [math]\Gamma''[/math] построим грамматику [math]\Gamma'[/math], в которой:

  • [math]N' = N'' \cup \{D\}[/math], где [math]D[/math] — новый символ,
  • [math]P'[/math] получаем из [math]P''[/math] заменой всех правил вида [math]\alpha \rightarrow \beta \in P''[/math], где [math]|\alpha| \gt |\beta|[/math] на правила вида [math]\alpha \rightarrow \beta D^{|\alpha| - |\beta|}[/math], и добавлением правила [math]D \rightarrow \varepsilon[/math].

Теперь все правила в [math]P'[/math] имеет требуемую форму.

Покажем, что [math]L(\Gamma') = L(\Gamma)[/math].

Заметим, что замена правила [math]\alpha \rightarrow \beta[/math] на [math]\alpha \rightarrow \beta D^{|\alpha| - |\beta|}[/math] не меняет язык грамматики, потому что [math]D[/math] переходит только в [math]\varepsilon[/math], а других правил для [math]D[/math] нет.

Тогда получаем, что [math]L(\Gamma) \subseteq L(\Gamma')[/math], аналогично обратные изменения не меняют язык, то есть [math]L(\Gamma') \subseteq L(\Gamma)[/math].
[math]\triangleleft[/math]


Определение:
Грамматика имеет порядок [math]n[/math], если [math]|\alpha| \leqslant n[/math] и [math]|\beta| \leqslant n[/math] для любого ее правила [math]\alpha \rightarrow \beta[/math].


Лемма (об уменьшении порядка грамматики):
Для любой грамматики [math]\Gamma = \langle \Sigma, N, S, P \rangle[/math] порядка [math]n \geqslant 3[/math], такой что: любое правило из [math]P'[/math] имеет вид [math]\alpha \rightarrow \beta[/math], где [math]\alpha \in (N')^+[/math] и [math]\beta \in (N')^+[/math] и [math]|\alpha| \leqslant |\beta|[/math] или [math]A \rightarrow a[/math] или [math]A \rightarrow \varepsilon[/math], где [math]A \in N'[/math] и [math]a \in T[/math] может быть построена грамматика [math]\Gamma' = \langle \Sigma, N', S, P' \rangle[/math] порядка [math]n - 1[/math] такая, что [math]L(\Gamma') = L(\Gamma)[/math].
Доказательство:
[math]\triangleright[/math]

Разделим [math]P[/math] на три подмножества:

[math]P_1 = \{ \alpha \rightarrow \beta \mid \alpha \rightarrow \beta \in P, |\alpha| \leqslant 2, |\beta| \leqslant 2 \}[/math],

[math]P_2 = \{ \alpha \rightarrow \beta \mid \alpha \rightarrow \beta \in P, |\alpha| \geqslant 2, |\beta| \geqslant 3 \}[/math],

[math]P_3 = \{ \alpha \rightarrow \beta \mid \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| \geqslant 3 \}[/math].

Очевидно, что [math]P = P_1 \cup P_2 \cup P_3[/math].

Построим [math]\Gamma'[/math] следующим образом:

  • Если правило [math]p \in P_2[/math], то оно имеет вид [math]AB\alpha' \rightarrow CDE\beta'[/math], где [math]\alpha' \in N^*[/math] и [math]\beta' \in N^*[/math].

Полагаем [math]N_p = \{ A_p, B_p \}[/math], [math]P_p = \{ AB \rightarrow A_pB_p, A_p \rightarrow C, B_p\alpha' \rightarrow DE\beta'\}[/math], где [math]A_p, B_p[/math] — дополнительные символы не из [math]N: \{A_p, B_p\} \cap \{A_q, B_q\} = 0[/math] для разных правил [math]p[/math] и [math]q[/math] из [math]P_2[/math].

  • Если правило [math]p \in P_3[/math], то оно имеет вид [math]A \rightarrow CDE\beta'[/math], где [math]\beta' \in N^*[/math].

Полагаем [math]N_p = \{B_p \}[/math], [math]P_p = \{A \rightarrow CB_p, B_p \rightarrow DE\beta'\}[/math], где [math]A_p, B_p[/math] — дополнительные символы.

Тогда [math]N' = N \bigcup\limits_{p \in (P_2 \cup P_3)} N_p[/math], [math]P' = P_1 \bigcup\limits_{p \in (P_2 \cup P_3)} P_p[/math].

Из построения очевидно, что [math]\Gamma'[/math] имеет порядок [math]n - 1[/math].

Покажем, что [math]L(\Gamma') = L(\Gamma)[/math].

Сначала докажем, что [math]L(\Gamma) \subseteq L(\Gamma')[/math]. Это следует из того, что:

  • все правила из [math]P_1[/math] применимы к обеим грамматикам,
  • шаг вывода [math]\gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1CDE\beta'\gamma_2[/math], благодаря правилу [math]p = AB\alpha \rightarrow CDE\beta' \in P_2[/math] в [math]\Gamma[/math]может быть использавано в [math]\Gamma'[/math] с помощью трех шагов:

[math]\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[/math], с использованием правил из [math]P_p[/math] и вывода [math]\gamma_1A\gamma_2 \Rightarrow \gamma_1CDE\beta'\gamma_2[/math] на основе правила [math]p = A\alpha \rightarrow CDE\beta' \in P_3[/math] в [math]G[/math], которое может быть применено в [math]G'[/math] с помощью трех шагов вывода: [math]\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[/math]. Таким образом, любой вывод в [math]\Gamma[/math] может быть преобразован в вывод в [math]\Gamma'[/math].

Чтобы показать обратное включение, рассмотрим вывод [math]w \in L(\Gamma')[/math] в [math]\Gamma'[/math], который содержит применение правил вида [math]AB \rightarrow A_pB_p[/math] для какого-то правила [math]p = AB\alpha' \rightarrow CDE\beta' \in P_2[/math]. Заметим, что другие два правила из [math]P_p[/math] могут быть применены только если правило [math]AB \rightarrow A_pB_p[/math] было применено в этом выводе ранее.

Данный вывод имеет вид (1):

[math]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^*[/math],

где [math]q_1[/math] — последовательность правил, примененых после [math]AB \rightarrow A_pB_p[/math] и до [math]A_p \rightarrow C[/math], которая осуществляет [math]\gamma_1 \Rightarrow^* \gamma_1'[/math] и [math]\gamma_2 \Rightarrow^* \gamma_2'[/math],

где [math]q_2[/math] — последовательность правил, осуществляющих [math]\gamma_1'C \Rightarrow^* \gamma_1''[/math] и [math]\gamma_2' \Rightarrow^* \gamma_2''[/math].

Или вид (2):

[math]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^*[/math],

где [math]q_1'[/math] — последовательность правил, которая осуществляет [math]\gamma_1 \Rightarrow^* \gamma_1'[/math] и [math]\gamma_2 \Rightarrow^* \gamma_2'[/math],

где [math]q_2'[/math] — последовательность правил, осуществляющих [math]\gamma_1' \Rightarrow^* \gamma_1''[/math] и [math]DE\beta'\gamma_2' \Rightarrow^* \gamma_2''[/math].

Таким образом, существует вывод: [math]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^*[/math], который получается из (1) заменой правил [math]P_p[/math] на применение [math]p = AB\alpha' \rightarrow CDE\beta \in P[/math]. Аналогично, в случае (2) мы можем заменить применение [math]P_p[/math] на [math]p[/math]. Кроме того, это верно и для применения [math]P_q,[/math] где [math]q \in P_3[/math].

Таким образом, для [math]r \in P_2 \cup P_3[/math] мы можем заменить все применения [math]P_r[/math] на [math]r[/math], то есть получаем вывод [math]w[/math], который состоит только из правил из [math]P[/math].

Тогда [math]w \in L(\Gamma)[/math] и [math]L(\Gamma') \subseteq L(\Gamma)[/math].
[math]\triangleleft[/math]
Теорема:
Любую грамматику [math]\Gamma[/math] можно преобразовать к грамматике [math]\Gamma_K[/math] в нормальной форме Куроды так, что [math]L(\Gamma) = L(\Gamma_K)[/math].
Доказательство:
[math]\triangleright[/math]

По лемме 1 построим из [math]\Gamma[/math] грамматику [math]\Gamma'[/math], затем по лемме 2 построим из [math]\Gamma'[/math] грамматику [math]\Gamma''[/math], Тогда [math]\Gamma''[/math] удовлетворит требованиям леммы 3.

Пусть [math]\Gamma''[/math] имеет порядок [math]n[/math]. Если [math]n = 2[/math], то [math]\Gamma''[/math] в нормальной форме Куроды и [math]\Gamma_K = \Gamma''[/math]. Если [math]n \geqslant 3[/math], построим [math]\Gamma'''[/math] порядка [math]n - 1[/math] из [math]\Gamma''[/math] по лемме 3. Понятно, что [math]\Gamma'''[/math] удовлетворяет условиям леммы 3.

Будем повторять процесс, пока не получим грамматику порядка [math]2[/math], которую и примем за [math]\Gamma_K[/math].
[math]\triangleleft[/math]

См. также

Источники информации