Изменения

|id = Reg1REG1

'''Множество регулярных языков''' (англ. ''set of regular languages'') <tex>\mathrm{RegREG}</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots, c_k \right\} </tex> {{---}} множество, которое может быть получено из языков, каждый из которых содержит единственное слово {{---}} <tex>c_i</tex> или <tex>\varepsilon</tex>, и пустого языка при помощи последовательных применений операций объединения, конкатенации или замыкания Клини и никаких других, то есть:

* Тогда <tex>\mathrm{RegREG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>.

'''Регулярное выражение''' (англ. ''regular expression'') над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> {{---}} порождающая система, задающая язык способ порождения языка над <tex> \Sigma </tex>. Определяется рекурсивно следующим образом:

* <tex>\varepsilon</tex> является регулярным выражением, задающим язык из одной пустой строки, а <tex>\varnothing</tex> {{---}} пустой язык.

|id = Reg2REG2

Множество <tex>\mathrm{R}</tex> будем называть ''надрегулярным'' множеством над алфавитом <tex> \Sigma </tex>, если:

Тогда '''множеством регулярных языков''' <tex> \mathrm{RegREG'} </tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... \ldots ,c_k \right\} </tex> называется пересечение всех надрегулярных множеств: <tex> \mathrm{Reg'}=\bigcap\limits_{\mathrm{R} \in \mathrm{REG}}\mathrm{R} </tex>над этим алфавитом.

Определения Классы языков [[#Reg1 REG1 | <tex>\mathrm{RegREG}</tex>]] и [[#Reg2 REG2 | <tex>\mathrm{RegREG'}</tex>]] эквивалентнынад одинаковым алфавитом совпадают.

Докажем, что <tex>\mathrm{RegREG} \subseteq \mathrm{RegREG'}</tex> и <tex>\mathrm{RegREG'} \subseteq \mathrm{RegREG}</tex>.

*'''<tex>\mathrm{RegREG} \subseteq \mathrm{RegREG'}</tex>'''По определению <tex>\mathrm{RegREG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>. Покажем, что <tex>\bigcup\limits_{i=0}^{\infty}\mathrm{R_i} \subseteq \mathrm{R}</tex>, где <tex>\mathrm{R}</tex> {{---}} любое надрегулярное множество. Для этого докажем по индукции по <tex>i</tex>, что <tex>\mathrm{R_i} \subseteq \mathrm{R}</tex> для любого <tex>i</tex>.

#: По определению надрегулярного множества для любых <tex>L_1, L_2 \in \mathrm{R_i} \subseteq \mathrm{R}</tex> верны утверждения: <tex>L_1 \cup L_2 \in \mathrm{R}, L_1L_2 \in \mathrm{R}, L_1^* \in \mathrm{R}</tex>. То есть: <tex>\left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in \mathrm{R_i}\right\} \subseteq \mathrm{R}</tex>. Вспоминая [[#Reg1 REG1 | определение]] <tex>\mathrm{R_{i + 1}}</tex> и предположение индукции (<tex>\mathrm{R_i} \subseteq \mathrm{R}</tex>), получаем, что <tex>\mathrm{R_{i + 1}} \subseteq \mathrm{R}</tex>.Так как <tex>\mathrm{RegREG} \subseteq R</tex> для любого надрегулярного множества <tex>R</tex>, получаем, что <tex> \mathrm{RegREG} \subseteq \mathrm{RegREG'} </tex>.

*'''<tex> \mathrm{RegREG'} \subseteq \mathrm{RegREG} </tex>'''Докажем, что <tex> \mathrm{RegREG} </tex> является надрегулярным множеством. Для этого проверим, выполняются ли свойства надрегулярного множества на нём: # <tex> \mathrm{R_0}\subseteq \mathrm{RegREG} </tex> {{---}} выполнено (по определению <tex> \mathrm{RegREG} </tex>).# Рассмотрим <tex> L_1, L_2 \in \mathrm{RegREG} </tex>. Так как <tex> \mathrm{RegREG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>, то найдутся такие индексы <tex> \exists i : </tex> и <tex>j</tex>, что <tex>L_1\in \mathrm{R_i} </tex> и <tex> \exists j : L_2 \in \mathrm{R_j} </tex>. Тогда из определения <tex> \mathrm{RegREG} </tex> следует, что <tex> L_1L_2 \in \mathrm{R_{max(i, j) + 1}}, L_1 \cup L_2\in \mathrm{R_{max(i, j) + 1}}, L_1^* \in \mathrm{R_{i + 1}}</tex>. Так как <tex> \mathrm{RegREG} = \bigcup\limits_{i=0}^{\infty}R_i</tex>, то получаем, что <tex> L_1L_2 \in \mathrm{RegREG}, L_1 \cup L_2\in \mathrm{RegREG}, L_1^* \in \mathrm{RegREG} </tex>. Следовательно, второе свойство также выполнено.Значит, <tex> \mathrm{RegREG} </tex> {{---}} надрегулярное множество. А так как <tex> \mathrm{RegREG'}=\bigcap\limits_{\mathrm{R} \in \mathrm{REG}}\mathrm{R}</tex>является пересечением всех надрегулярных множеств, то <tex> \mathrm{RegREG'} \subseteq \mathrm{RegREG} </tex>.