170
правок
Изменения
Нет описания правки
== Регулярные языки: два определения и их эквивалентность ==
{{Определение
|id = Reg1REG1
|definition =
'''Множество регулярных языков''' <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{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{RegREG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>.
}}
{{Определение
|id = Reg2REG2
|definition =
Пусть задан алфавит <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </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{RegREG'} </tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... ,c_k \right\} </tex> называется пересечение всех надрегулярных множеств: <tex> \mathrm{Reg'}=\bigcap\limits_{\mathrm{R} \in \mathrm{REG}}\mathrm{R} </tex>.
}}
{{Теорема
|statement=
|proof=
Докажем, что <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>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{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>i</tex> и <tex>j</tex>, что <tex>L_1 \in \mathrm{R_i}</tex> и <tex>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>.
}}
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
