*'''{{Определение 1: '''|definition =Будем обозначать через <texmath>Reg_0 Reg_t - </texmath> языки <texmath>kt</texmath>-го поколения (<tex>k</tex> - размер алфавита). Рассмотрим язык языки нулевого поколения: <texmath>Reg_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} ... \left\{c_k \right\} \right\}</texmath>, (<math> k - языки нулевого поколения</math>размер алфавита). Пусть имеем <texmath>Reg_i</texmath>. Построим <texmath>Reg_{i+1} = Reg_i \cup \left\{L \cup M, LM, L^* \right\}</tex>, где <tex>| L, M \in Reg_i\right\}</texmath>. Тогда по определению <em>множество всех регулярных языков</em>: <texmath>Reg = \bigcup_{i=0}^{\infty}Reg_i</texmath>.*'''}} {{Определение 2: '''|definition =Пусть <texmath>A=\left\{L \right\}</texmath>. <texmath>A - </texmath> хорошее, если <texcenter>1) <math> Reg_0 \subset A </math></center> <center> 2) <math> L_1, L_2 \in A \rightarrow Rightarrow L_1 \cap L_2 \in A, L_1L_2 \in A, L_1^* \in A </texmath></center> Тогда <em>регулярным языком</em> называется <texmath>Reg'=\bigcup_{\text{A-хорошее}}A</texmath>.}} {{Теорема|statement=Определения 1 и 2 эквивалентны.|proof=Докажем, что <math>Reg \subset Reg'</math> и <math>Reg' \subset Reg</math>. '''<math>Reg \subset Reg'</math>:''' будем доказывать по индукции. Заметим, что <math>Reg_0 \subset Reg'</math> по определению. Пусть <math>Reg_i \subset Reg'</math>. Тогда <math>Reg_{i+1} \subset Reg'</math>. '''<math>Reg' \subset Reg</math>:'''по определению <math>Reg - </math>хорошее множество.}}
