Регулярные языки: два определения и их эквивалентность

• Определение 1: Будем обозначать через [math]Reg_0 - [/math] языки [math]k[/math]-го поколения ([math]k[/math] - размер алфавита). Рассмотрим язык [math]Reg_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} ... \left\{c_k \right\} \right\}[/math] - языки нулевого поколения. Пусть имеем [math]Reg_i[/math]. Построим [math]Reg_{i+1} = Reg_i \cup \left\{L \cup M, LM, L^* \right\}[/math], где [math]L, M \in Reg_i[/math]. Тогда по определению множество всех регулярных языков: [math]Reg = \bigcup_{i=0}^{\infty}Reg_i[/math].
• Определение 2: Пусть [math]A=\left\{L \right\}[/math]. [math]A - [/math] хорошее, если [math]1) Reg_0 \subset A 2) L_1, L_2 \in A \rightarrow L_1 \cap L_2 \in A, L_1L_2 \in A, L_1^* \in A [/math] Тогда регулярным языком называется [math]Reg'=\bigcup_{A-хорошее}A[/math].