Изменения

Будем обозначать через <mathtex>Reg_t - </mathtex> языки <mathtex>t</mathtex>-го поколения.  Рассмотрим языки нулевого поколения: <mathtex>Reg_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} ... \left\{c_k \right\} \right\}</mathtex>, (<mathtex>k - </mathtex>размер алфавита).  Пусть имеем <mathtex>Reg_i</mathtex>. Построим <mathtex>Reg_{i+1} = Reg_i \cup \left\{L \cup M, LM, L^*| L, M \in Reg_i\right\}</mathtex>.  Тогда по определению <em>множество всех регулярных языков</em>: <mathtex>Reg = \bigcup_{i=0}^{\infty}Reg_i</mathtex>.

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

#<center> 1) <mathtex> Reg_0 \subset A </mathtex>#<tex>L_1, L_2 \in A \Rightarrow L_1 \cup L_2 \in A, L_1L_2 \in A, L_1^* \in A</centertex>

<center> 2) <math> L_1, L_2 \in A \Rightarrow L_1 \cap L_2 \in A, L_1L_2 \in A, L_1^* \in A </math></center>Тогда <em>регулярным языкоммножеством регулярных языков</em> называется будем называть <mathtex>Reg'=\bigcap_{\text{A- xop.}}A</mathtex>.

Докажем, что <mathtex>Reg \subset Reg'</mathtex> и <mathtex>Reg' \subset Reg</mathtex>. *'''<tex>Reg \subset Reg'</tex>''' Будем доказывать по индукции. База индукции: из первого свойства хорошего языка получаем, что <tex>\forall A: Reg_0 \subset A</tex>. Поэтому из того, что <tex>Reg'</tex> есть пересечение всех хороших языков получаем: <tex>Reg'=\bigcap_{\text{A- xop.}}A \Rightarrow Reg_0 \subset Reg'</tex>. Индукционный переход. Пусть <tex>Reg_i \subset Reg'</tex>. Докажем, что <tex>Reg_{i+1} \subset Reg'</tex>. Действительно, так как <tex>Reg_i \subset Reg'</tex>, то <tex>\forall A: Reg_i \subset A</tex>. Рассмотрим способ построения <tex>Reg_{i+1}</tex>: <tex>Reg_{i+1} = Reg_i \cup \left\{L \cup M, LM, L^*| L, M \in Reg_i\right\}</tex>. Тогда, принимая во внимание вышесказанное, получаем, что <tex>\forall A: L, M \in A</tex>. Тогда, принимая во внимание второе свойство хорошего множества, получаем, что операция образования <tex>Reg_{i+1}</tex> не вывела нас за рамки хорошего множества, так как полученное множество осталось замкнутым относительно операций объединения, конкатенации и замыкания Клини. Таким образом получили, что если <tex>Reg_i \subset Reg' \Rightarrow Reg_{i+1} \subset Reg'</tex>. Значит <tex>Reg \subset Reg'</tex>. *'''<tex>Reg' \subset Reg</tex>''' По определению <tex>Reg</tex> получаем, что # <tex> Reg_0 \subset Reg </tex>

*'''# <mathtex>L_1, L_2 \in Reg \subset Rightarrow L_1 \cup L_2 \in Reg, L_1L_2 \in Reg, L_1^* \in Reg'</mathtex>:'''

будем доказывать по индукции. Заметим, что Значит <mathtex>Reg_0 \subset Reg'- </mathtex> по определениюхорошее множество. Пусть А так как <mathtex>Reg_i \subset Reg'</math>. Тогда <math>Reg_=\bigcap_{i+1} \subset Reg'</math> по способу построения множества <math>Reg_text{i+1}</math>. Действительно, из того, что <math>Reg_i \subset Reg'</math> следует, что <math>\forall A: Reg_i \subset A</math>- xop. А так как по построению <math>Reg_{i+1}}A</mathtex> останется хорошим, то и <mathtex>\forall A: Reg_{i+1} Reg' \subset AReg</mathtex>.

*'''<math>Reg' \subset Reg</math>:'''по определению <math>Reg - </math>хорошее множествоТаким образом, теорема доказана.