142
правки
Изменения
Нет описания правки
Определения 1 и 2 эквивалентны.
|proof=
Докажем, что <tex>Reg \subset subseteq Reg'</tex> и <tex>Reg' \subset subseteq Reg</tex>.
*'''<tex>Reg \subset subseteq Reg'</tex>'''По определению <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>. Покажем, что <tex>\bigcup\limits_{i=0}^{\infty}R_i \subset subseteq R</tex>, где <tex>R</tex> {{---}} любое надрегулярное множество. Для этого докажем по индукции по <tex>i</tex>, что <tex>R_i \subset subseteq R</tex>.
# База: <tex>i = 0</tex>.
#: <tex>R_0 \subset subseteq R</tex> по определению надрегулярного множества.# Переход: известно, что <tex>R_i \subset subseteq R</tex>, докажем, что <tex>R_{i+1} \subset subseteq R</tex>.#: По определению надрегулярного множества для любых <tex>L_1, L_2 \in R_i \subset subseteq R</tex> верны утверждения: <tex>L_1 \cup L_2 \in R, L_1L_2 \in R, L_1^* \in R</tex>. То есть: <tex>\left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in R_i\right\} \subset subseteq R</tex>. Вспоминая определение <tex>R_{i+1}</tex> и предположение индукции (<tex>R_i \subset subseteq R</tex>), получаем, что <tex>R_{i+1} \subset subseteq R</tex>.Так как <tex>Reg \subset subseteq R</tex> для любого надрегулярного множества <tex>R</tex>, получаем, что <tex> Reg \bigcup\limits_{i=0}^{\infty}R_i \subset subseteq Reg' </tex>.
*'''<tex>Reg' \subset subseteq Reg</tex>'''
Докажем, что <tex> Reg </tex> является надрегулярным множеством. Для этого проверим, выполняются ли свойства надрегулярного множества на нём:
# <tex> R_0 \subset subseteq Reg </tex> {{---}} выполнено (по определению <tex>Reg</tex>).
# Рассмотрим <tex>L_1, L_2 \in Reg</tex>. Так как <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>, то <tex> \exists i : L_1\in R_i </tex> и <tex> \exists j : L_2 \in R_j </tex>. Тогда из определения <tex> Reg </tex> следует, что <tex> L_1L_2 \in R_{max(i, j)+1}, L_1 \cup L_2\in R_{max(i, j)+1}, L_1^* \in R_{i + 1}</tex>. Так как <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>, то получаем, что <tex> L_1L_2 \in Reg, L_1 \cup L_2\in Reg, L_1^* \in Reg </tex>. Следовательно, второе свойство также выполнено.
Значит, <tex>Reg</tex> {{---}} надрегулярное множество. А так как <tex>Reg'=\bigcap\limits_{\text{R- nadreg}}R</tex>, то <tex>Reg' \subset subseteq Reg</tex>.
}}
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
