Изменения

Будем обозначать через '''Множество регулярных языков''' (англ. ''set of regular languages'') <tex>\mathrm{REG}</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots, c_k \right\} </tex>Reg_t {{- --}} множество, которое может быть получено из языков, каждый из которых содержит единственное слово {{---}} <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>t\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 = '''Регулярное выражение''' (англ. ''regular expression'') над алфавитом <tex>Reg_0\Sigma =\left\{\varnothingc_1, \left\{\varepsilon \right\}c_2, \left\{c_1 \right\}ldots , \left\{c_2 \right\} ... \left\{c_k \right\} \right\}</tex>, ({{---}} способ порождения языка над <tex>k - \Sigma</tex>размер алфавита).Определяется рекурсивно следующим образом:

Пусть имеем * Для любого <tex>i</tex> слово <tex>c_i</tex> является регулярным выражением, задающим язык из одного слова <tex>Reg_ic_i</tex>. Построим * <tex>\varepsilon</tex>Reg_является регулярным выражением, задающим язык из одной пустой строки, а <tex>\varnothing</tex> {{i+1---}} = Reg_i пустой язык.* Если <tex>\cup alpha_1</tex> и <tex>\alpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, то <tex>(\leftalpha_1)|(\alpha_2)</tex> {L {---}} регулярное выражение, задающее <tex>L_1 \cup Mbigcup L_2</tex>.* Если <tex>\alpha_1</tex> и <tex>\alpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, LMто <tex>(\alpha_1)(\alpha_2)</tex> {{---}} регулярное выражение, L^задающее <tex>L_1L_2</tex>.*| LЕсли <tex>\alpha_1</tex> является регулярным выражением, задающим язык <tex>L_1</tex>, M \in Reg_i\rightто <tex>(\alpha_1)^*</tex> {{---}}регулярное выражение, задающее <tex>L_1^*</tex>.* Операции указаны в порядке возрастания приоритета, при этом скобки повышают приоритет аналогично арифметическим выражениям.}}

Тогда по определению <em>{{Утверждение|statement = По построению очевидно, что множество языков, порождаемых регулярными выражениями, совпадает со множеством регулярных языков</em>: <tex>Reg = \bigcup_{i=0}^{\infty}Reg_i</tex>.

Пусть задан алфавит <tex>A - \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> множество языков. Будем говорить, что Множество <tex>A - \mathrm{R}</tex> хорошее, если выполнены следующие свойства: языки нулевого поколения являются подмножеством будем называть ''надрегулярным'' множеством над алфавитом <tex>A\Sigma </tex> и множество <tex>A</tex> замкнуто относительно операций объединения, конкатенации и замыкания Клини, т.е.если:

#<tex>Reg_0 \mathrm{R_0} \subset A\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 A \mathrm{R} \Rightarrow L_1 \cup L_2 \in A\mathrm{R}, L_1L_2 \in A\mathrm{R}, L_1^* \in A\mathrm{R}</tex>.

Тогда <em>'''множеством регулярных языков''' <tex> \mathrm{REG'} </emtex> будем называть над алфавитом <tex>Reg'\Sigma =\bigcap_left\{c_1, c_2, \ldots ,c_k \right\text{A- xop.}}A</tex>называется пересечение всех надрегулярных множеств над этим алфавитом.

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

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

*'''<tex>Reg \subset Regmathrm{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>i = 0</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>\forall A: Reg_0 mathrm{REG'} \subseteq \subset Amathrm{REG} </tex>. Поэтому из того'''Докажем, что <tex>Reg'\mathrm{REG} </tex> есть пересечение всех хороших языков получаемявляется надрегулярным множеством. Для этого проверим, выполняются ли свойства надрегулярного множества на нём: # <tex>Reg'=\bigcap_mathrm{R_0}\subseteq \textmathrm{REG} </tex> {{A- xop.--}}A выполнено (по определению <tex> \Rightarrow Reg_0 \subset Reg'mathrm{REG} </tex>). Индукционный переход: пусть # Рассмотрим <tex>Reg_i L_1, L_2 \in \subset Reg'mathrm{REG} </tex>. Докажем, что Так как <tex>Reg_\mathrm{REG} = \bigcup\limits_{i+1=0}^{\infty} \subset Reg'mathrm{R_i}</tex>, то найдутся такие индексы <tex>i</tex> и <tex>j</tex>. Действительно, так как что <tex>Reg_i L_1 \in \subset Reg'mathrm{R_i}</tex>, то и <tex>L_2 \forall A: Reg_i in \subset Amathrm{R_j}</tex>. Рассмотрим способ построения Тогда из определения <tex>Reg_\mathrm{i+1REG}</tex>: следует, что <tex>Reg_L_1L_2 \in \mathrm{R_{max(i, j) +1} = Reg_i }, L_1 \cup L_2\leftin \mathrm{R_{L \cup Mmax(i, LMj) + 1}}, LL_1^*| L, M \in Reg_i\rightmathrm{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 \forall A: Lmathrm{REG}, M L_1^* \in A\mathrm{REG} </tex>. Следовательно, второе свойство также выполнено.Значит, <tex> \mathrm{REG} </tex> {{---}} надрегулярное множество. А так как <tex> \mathrm{REG'}</tex> является пересечением всех надрегулярных множеств, то <tex> \mathrm{REG'} \subseteq \mathrm{REG} </tex>.}}

Так как <tex>A - </tex>хорошее, получаем, что <tex>Reg_{i+1}</tex> тоже содержится в <tex>A</tex>, т.е. <tex>A - xop. \Rightarrow Reg_{i+1} \subset A</tex>. Таким образом получили, что если <tex>Reg_i \subset Reg' \Rightarrow Reg_{i+1} \subset Reg'</tex>. Значит <tex>Reg \subset Reg'</tex>== См.также ==* [[Детерминированные конечные автоматы]]

По определению <tex>Reg<* [http:/tex> получаем, что/en.wikipedia.org/wiki/Regular_language Wikipedia {{---}} Regular language]* [http://en.wikipedia.org/wiki/Regular_expression Wikipedia {{---}} Regular expression]* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA Википедия {{---}} Регулярный язык]* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F#.D0.92_.D1.82.D0.B5.D0.BE.D1.80.D0.B8.D0.B8_.D1.84.D0.BE.D1.80.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.8F.D0.B7.D1.8B.D0.BA.D0.BE.D0.B2 Википедия {{---}} Регулярные выражения]

# <tex> Reg_0 \subset Reg </tex>[[Категория: Теория формальных языков]] # <tex> L_1, L_2 \in Reg \Rightarrow L_1 \cup L_2 \in Reg, L_1L_2 \in Reg, L_1^* \in Reg </tex>  Значит <tex>Reg - </tex>хорошее множество. А так как <tex>Reg'=\bigcap_{\text{A- xop.}}A</tex>, то <tex>Reg' \subset Reg</tex>. Таким образом, теорема доказана.}}[[Категория: Автоматы и регулярные языки]]