275
правок
Изменения
м
Нет описания правки
{{Лемма
|about=об удалении терминалов
|statement = Для любой грамматики <tex>G \Gamma = \langle \Sigma, N, S, P \rangle</tex> может быть построена грамматика <tex>G\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 \Sigma</tex>,
* <tex>L(G\Gamma') = L(G\Gamma)</tex>Кроме того, если <tex>G\Gamma</tex> контекстно-свободна или контекстно-зависима, то и <tex>G\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>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\Gamma') = L(G\Gamma)</tex>.
Пусть <tex>w \in L(G\Gamma)</tex>. Тогда в <tex>G\Gamma</tex> существует вывод <tex>S = w_0 \Rightarrow w_1 \Rightarrow ... \Rightarrow w_n \Rightarrow w</tex>.
Согласно конструкции <tex>P'</tex>, в <tex>G\Gamma'</tex> существует вывод <tex>S = w_0' \Rightarrow w_1' \Rightarrow w_2' \Rightarrow ... \Rightarrow w_n' = v_0 \Rightarrow v_1 \Rightarrow v_2 \Rightarrow ... \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>a' \rightarrow a</tex> полученное <tex>a</tex> не может быть использовано при применении правил из <tex>P'</tex>.
Изменение порядка вывода не меняет язык, то есть в <tex>G\Gamma'</tex> существует вывод: <tex>S = x_0' \Rightarrow x_1' \Rightarrow ... \Rightarrow x_r' \Rightarrow x' \Rightarrow y_1 \Rightarrow y_2 \Rightarrow ... \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 ... \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, S, P \rangle</tex> может быть построена грамматика <tex>G\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| \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=
Сначала по <tex>G\Gamma</tex> построим грамматику <tex>G\Gamma'' = \langle \Sigma, N'', S, P'' \rangle</tex>, как в доказательстве леммы 1. По <tex>G\Gamma''</tex> построим грамматику <tex>G\Gamma'</tex>, в которой:
* <tex>N' = N'' \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 \beta D^{|\alpha| - |\beta|}</tex>, и добавлением правила <tex>D \rightarrow \varepsilon</tex>.
Теперь все правила в <tex>P'</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>\varepsilon</tex>, а других правил для <tex>D</tex> нет.
Тогда получаем, что <tex>L(G\Gamma) \subseteq L(G\Gamma')</tex>, аналогично обратные изменения не меняют язык, то есть <tex>L(G\Gamma') \subseteq L(G\Gamma)</tex>.
}}
|about=об уменьшении порядка грамматики
|statement=
Для любой грамматики <tex>G \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>G\Gamma' = \langle \Sigma, N', S, P' \rangle</tex> порядка <tex>n - 1</tex> такая, что <tex>L(G\Gamma') = L(G\Gamma)</tex>.
|proof=
Разделим <tex>P</tex> на три подмножества:
Очевидно, что <tex>P = P_1 \cup P_2 \cup P_3</tex>.
Построим <tex>G\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' = 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>G\Gamma'</tex> имеет порядок <tex>n - 1</tex>.
Покажем, что <tex>L(G\Gamma') = L(G\Gamma)</tex>.
Сначала докажем, что <tex>L(G\Gamma) \subseteq L(G\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>G\Gamma</tex>может быть использавано в <tex>G\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>G\Gamma</tex> может быть преобразован в вывод в <tex>G\Gamma'</tex>.
Чтобы показать обратное включение, рассмотрим вывод <tex>w \in L(G\Gamma')</tex> в <tex>G\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>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(G\Gamma)</tex> и <tex>L(G\Gamma') \subseteq L(G\Gamma)</tex>.
}}
{{Теорема
|statement=
Любую грамматику <tex>G\Gamma</tex> можно преобразовать к грамматике <tex>G_K\Gamma_K</tex> в нормальной форме Куроды так, что <tex>L(G\Gamma) = L(G_K\Gamma_K)</tex>.
|proof=
По лемме 1 построим из <tex>G\Gamma</tex> грамматику <tex>G\Gamma'</tex>, затем по лемме 2 построим из <tex>G\Gamma'</tex> грамматику <tex>G\Gamma''</tex>, Тогда <tex>G\Gamma''</tex> удовлетворит требованиям леммы 3.
Пусть <tex>G\Gamma''</tex> имеет порядок <tex>n</tex>. Если <tex>n = 2</tex>, то <tex>G\Gamma''</tex> в нормальной форме Куроды и <tex>G_K \Gamma_K = G\Gamma''</tex>. Если <tex>n \geqslant 3</tex>, построим <tex>G\Gamma'''</tex> порядка <tex>n - 1</tex> из <tex>G\Gamma''</tex> по лемме 3.Понятно, что <tex>G\Gamma'''</tex> удовлетворяет условиям леммы 3. Будем повторять процесс, пока не получим грамматику порядка <tex>2</tex>, которую и примем за <tex>G_K\Gamma_K</tex>.
}}
