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

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

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

Регулярный язык [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]Reg = \bigcup\limits_{i=0}^{\infty}R_i[/math]. Рассмотрим [math] \forall i [/math] и любой надрез [math] R [/math]: [math]R_i \subset R[/math] (следует из определения [math]R_i[/math] и определения надреза). Это выполнимо для любого надрезa [math] R \Rightarrow R_i \subset Reg'[/math]. Так как это выполнено для [math] \forall i \Rightarrow \bigcup\limits_{i=0}^{\infty}R_i \subset Reg' [/math]. [math]Reg' \subset Reg[/math] Из определения [math]Reg[/math] следует, что: [math] R_0 \subset Reg [/math]. [math] L_1, L_2 \in Reg \Rightarrow \exists i [/math], что [math] L_1\in R_i [/math] и [math] \exists j [/math] , что [math] L_2 \in R_j \Rightarrow 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}[/math] [math] \Rightarrow L_1L_2 \in Reg, L_1 \cup L_2\in Reg, L_1^* \in Reg [/math]. Значит [math]Reg[/math] — надрез. А так как [math]Reg'=\bigcap\limits_{\text{R- nadrez}}R[/math], то [math]Reg' \subset Reg[/math].

[math]\triangleleft[/math]