Изменения
Нет описания правки
|definition =
Пусть задан алфавит <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex>.
Множество <tex>R</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>Reg'</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... ,c_k \right\} </tex> называется пересечение всех надрезовнадрегулярных множеств: <tex>Reg'=\bigcap\limits_{R - nadreznadreg}R</tex>.
}}
По определению <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>.
Рассмотрим любое множество <tex> R_i </tex> и любой надрез любое надрегулярное множество<tex> R </tex>: <tex>R_i \subset R</tex> (следует из определения <tex>R_i</tex> и определения надрезанадрегулярного множества).
Это верно для любого надрезa надрегулярного множества <tex>R</tex>, следовательно <tex> R_i \subset Reg'</tex>. Это выполнено для любого <tex> R_i </tex>, значит <tex> \bigcup\limits_{i=0}^{\infty}R_i \subset Reg' </tex>.
*'''<tex>Reg' \subset Reg</tex>'''
Докажем, что <tex> Reg </tex> является надрезомнадрегулярным множеством. Для этого проверим, выполняются ли свойства надреза надрегулярного множества на нём:
# <tex> R_0 \subset Reg </tex> {{---}} выполнено (по определению <tex>Reg</tex>).
# Рассмотрим <tex>L_1, L_2 \in Reg</tex>. Так как <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>, то <tex> \exists i : L_1\in R_i </tex> и <tex> \exists j : L_2 \in R_j </tex>. Тогда из определения <tex> Reg </tex> следует, что <tex> L_1L_2 \in R_{max(i, j)+1}, L_1 \cup L_2\in R_{max(i, j)+1}, L_1^* \in R_{i + 1}</tex>. Так как <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>, то получаем, что <tex> L_1L_2 \in Reg, L_1 \cup L_2\in Reg, L_1^* \in Reg </tex>. Следовательно, второе свойство также выполнено.
Значит, <tex>Reg</tex> {{---}} надрезнадрегулярное множество. А так как <tex>Reg'=\bigcap\limits_{\text{R- nadreznadreg}}R</tex>, то <tex>Reg' \subset Reg</tex>.
}}
= Литература =
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
