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

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

Определение:

Регулярный язык [math] Reg [/math] над алфавитом [math] \Sigma = \left\{c_1, c_2, ... ,c_k \right\} [/math] — язык, который может быть получен из букв алфавита при помощи последовательных применений операций объединения, конкатенации или итерации и никаких других, т.е.: Обозначим [math]R_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} ... \left\{c_k \right\} \right\}[/math] Определим [math]R_{i+1}[/math] через [math]R_i[/math]: [math]R_{i+1} = R_i \cup \left\{L_1 \cup L_2, L_1L_2, L_1^*| L_1, L_2 \in R_i\right\}[/math]. Тогда: [math]Reg = \bigcup\limits_{i=0}^{\infty}R_i[/math]

Определение:

Пусть задан алфавит [math] \Sigma = \left\{c_1, c_2, ... ,c_k \right\} [/math]. Множество [math]R[/math] будем называть надрезом, если: [math]R_0 \subset R[/math], где [math]R_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} ... \left\{c_k \right\} \right\}[/math] [math] L_1, L_2 \in R \Rightarrow L_1 \cup L_2 \in R, L_1L_2 \in R, L_1^* \in R[/math] Тогда регулярным языком [math]Reg'[/math] над алфавитом [math] \Sigma = \left\{c_1, c_2, ... ,c_k \right\} [/math] называется пересечение всех надрезов: [math]Reg'=\bigcap\limits_{R - nadrez}R[/math]

Теорема:

Определения 1 и 2 эквивалентны.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]