Изменения

'''Множество регулярных языков''' <tex> \mathrm{Reg }</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> {{---}} множество языков, которое может быть получено из языков, каждый из которых содержит единственное слово {{---}} <tex>c_i</tex> или <tex>\varepsilon</tex>, и пустого языка при помощи последовательных применений операций объединения, конкатенации или замыкания Клини и никаких других, то есть:* Определим регулярные языки нулевого уровня как <tex> \mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} , \ldots, \left\{c_k \right\} \right\} </tex>.* Регулярные языки ненулевого уровня определим рекуррентным соотношением: <tex> \mathrm{R_{i+1}} = \mathrm{R_i} \cup \left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in \mathrm{R_i}\right\} </tex>.* Тогда <tex>\mathrm{Reg} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>.}}

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

определим * Для любого <tex>R_{i+1}</tex> через слово <tex>c_i</tex> является регулярным выражением, задающим язык из одного слова <tex>R_ic_i</tex>: .* <tex>R_{i+1} = R_i \cup varepsilon</tex> является регулярным выражением, задающим язык из одной пустой строки.* Если <tex>\leftalpha_1</tex> и <tex>\{alpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1 \cup </tex> и <tex>L_2</tex> соответственно, L_1L_2то <tex>(\alpha_1)|(\alpha_2)</tex> {{---}} регулярное выражение, задающее <tex>L_1^\bigcup L_2</tex>.* | Если <tex>\alpha_1</tex> и <tex>\alpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, L_2 то <tex>(\in R_i\rightalpha_1)(\alpha_2)</tex> {{---}}регулярное выражение, задающее <tex>L_1L_2</tex>,.тогда: * Если <tex>Reg = \bigcupalpha_1</tex> является регулярным выражением, задающим язык <tex>L_1</tex>, то <tex>(\limits_alpha_1)^*</tex> {{i=0---}}регулярное выражение, задающее <tex>L_1^{\infty}R_i*</tex>.* Операции указаны в порядке возрастания приоритета, при этом скобки повышают приоритет аналогично арифметическим выражениям.}} {{Утверждение|statement = По построению очевидно, что множество языков, порождаемых регулярными выражениями, совпадает со множеством регулярных языков.

Множество <tex>\mathrm{R}</tex> будем называть надрегулярным, если: #<tex>\mathrm{R_0} \subset \mathrm{R}</tex>, где <tex>\mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\}, \ldots, \left\{c_k \right\} \right\}</tex>,#<tex> L_1, L_2 \in \mathrm{R} \Rightarrow L_1 \cup L_2 \in \mathrm{R}, L_1L_2 \in \mathrm{R}, L_1^* \in \mathrm{R}</tex>.Семейство всех надрегулярных множеств обозначим <tex> \mathrm{REG} </tex>.

#<tex>R_0 \subset R</tex>, где <tex>R_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\}, \ldots, \left\{c_k \right\} \right\}</tex>,#<tex> L_1, L_2 \in R \Rightarrow L_1 \cup L_2 \in R, L_1L_2 \in R, L_1^* \in R</tex>.Тогда '''множеством регулярных языков''' <tex>\mathrm{Reg'} </tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... ,c_k \right\} </tex> называется пересечение всех надрегулярных множеств: <tex>\mathrm{Reg'}=\bigcap\limits_{\mathrm{R - nadreg}\in \mathrm{REG}}\mathrm{R} </tex>.

Определения 1 языков [[#Reg1 | <tex>\mathrm{Reg}</tex>]] и 2 [[#Reg2 | <tex>\mathrm{Reg'}</tex>]] эквивалентны.

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

*'''<tex>\mathrm{Reg } \subseteq \mathrm{Reg'}</tex>'''По определению <tex>\mathrm{Reg } = \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>\mathrm{R_0 } \subseteq \mathrm{R}</tex> по определению надрегулярного множества.# Переход: известно, что <tex>\mathrm{R_i } \subseteq \mathrm{R}</tex>, докажем, что <tex>\mathrm{R_{i+1}} \subseteq \mathrm{R}</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 | определение ]] <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{Reg } \subseteq R</tex> для любого надрегулярного множества <tex>R</tex>, получаем, что <tex> \mathrm{Reg } \subseteq \mathrm{Reg' } </tex>.

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