170
правок
Изменения
Нет описания правки
{{Определение
|definition =
'''Регулярное выражение''' над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> {{---}} порождающая система, задающая язык способ порождения языка над <tex> \Sigma </tex>. Определяется рекурсивно следующим образом:
* Для любого <tex>i</tex> слово <tex>c_i</tex> является регулярным выражением, задающим язык из одного слова <tex>c_i</tex>.
* <tex>\varepsilon</tex> является регулярным выражением, задающим язык из одной пустой строки, а <tex>\varnothing</tex> {{---}} пустой язык.
* Если <tex>\alpha_1</tex> и <tex>\alpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, то <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> соответственно, то <tex>(\alpha_1)(\alpha_2)</tex> {{---}} регулярное выражение, задающее <tex>L_1L_2</tex>.
{{Теорема
|statement=
Определения языков множеств [[#Reg1 | <tex>\mathrm{Reg}</tex>]] и [[#Reg2 | <tex>\mathrm{Reg'}</tex>]] эквивалентны.
|proof=
Докажем, что <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 : </tex> и <tex>j</tex>, что <tex>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_{\mathrm{R} \in \mathrm{REG}}\mathrm{R}</tex>, то <tex> \mathrm{Reg'} \subseteq \mathrm{Reg} </tex>.
}}
