Изменения

Будем обозначать через '''Множество регулярных языков''' (англ. ''set of regular languages'') <tex>\mathrm{REG}</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots, c_k \right\} <math/tex>Reg_t {{-- -}} множество, которое может быть получено из языков, каждый из которых содержит единственное слово {{---}} <tex>c_i</mathtex> языки или <mathtex>t\varepsilon</mathtex>-го поколения. Рассмотрим , и пустого языка при помощи последовательных применений операций объединения, конкатенации или замыкания Клини и никаких других, то есть:* Определим регулярные языки нулевого поколения: уровня как <mathtex>Reg_0\mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} ... , \ldots, \left\{c_k \right\} \right\}</mathtex>, (<math>k - </math>размер алфавита). Пусть имеем * Регулярные языки ненулевого уровня определим рекуррентным соотношением: <mathtex>Reg_i</math>. Построим <math>Reg_\mathrm{R_{i+1}} = Reg_i \mathrm{R_i} \cup \left\{L L_1 \cup ML_2, LML_1L_2, LL_1^*| LL_1, M L_2 \in Reg_i\mathrm{R_i}\right\}</mathtex>. * Тогда по определению <emtex>множество всех регулярных языков</em>: <math>Reg \mathrm{REG} = \bigcup_bigcup\limits_{i=0}^{\infty}Reg_i\mathrm{R_i}</mathtex>.

Пусть задан алфавит <mathtex>A\Sigma =\left\{L c_1, c_2, \ldots ,c_k \right\}</mathtex>. Множество <tex>\mathrm{R}<math/tex>A - будем называть ''надрегулярным'' множеством над алфавитом <tex> \Sigma </mathtex> хорошее, если:

#<centertex> 1) \mathrm{R_0} \subset \mathrm{R}<math/tex> Reg_0 , где <tex>\mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\subset A }, \left\{c_1 \right\}, \left\{c_2 \right\}, \ldots, \left\{c_k \right\} \right\}</mathtex>,#<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}</centertex>.

Тогда '''множеством регулярных языков''' <centertex> 2) \mathrm{REG'} <math/tex> над алфавитом <tex> L_1, L_2 \in A Sigma = \Rightarrow L_1 left\cap L_2 \in A{c_1, c_2, L_1L_2 \in Aldots , L_1^* c_k \in A </math></center>Тогда <em>регулярным языком</em> называется <math>Reg'=\bigcup_{right\text{A- хорошее}}A</mathtex>называется пересечение всех надрегулярных множеств над этим алфавитом.

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

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

*'''<mathtex>Reg \subset Regmathrm{REG} \subseteq \mathrm{REG'}</mathtex>:'''По определению <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> \mathrm{REG'} \subseteq \mathrm{REG} </tex>'''Докажем, что <tex> \mathrm{REG} </tex> является надрегулярным множеством. ЗаметимДля этого проверим, что выполняются ли свойства надрегулярного множества на нём: # <mathtex>Reg_0 \subset Reg'mathrm{R_0}\subseteq \mathrm{REG} </mathtex> {{---}} выполнено (по определению<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>i</tex> и <tex>j</tex>, что <tex>L_1 \in \mathrm{R_i}<math/tex>Reg_i и <tex>L_2 \subset Reg'in \mathrm{R_j}</mathtex>. Тогда из определения <tex> \mathrm{REG} <math/tex>Reg_следует, что <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'}</tex> является пересечением всех надрегулярных множеств, то <tex> \subset Regmathrm{REG'} \subseteq \mathrm{REG} </mathtex>.}}

'''<math>Reg' \subset Reg<== См. также ==* [[Детерминированные конечные автоматы]] == Источники информации == * [http:/math>/en.wikipedia.org/wiki/Regular_language Wikipedia {{---}} Regular language]* [http:'''//en.wikipedia.org/wiki/Regular_expression Wikipedia {{---}} Regular expression]по определению <math>Reg * [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/math>хорошее множество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 Википедия {{---}}Регулярные выражения] [[Категория: Теория формальных языков]][[Категория: Автоматы и регулярные языки]]