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

Материал из Викиконспекты
Перейти к: навигация, поиск
(изменены определения)
(изменено доказательство теоремы)
Строка 7: Строка 7:
  
 
Определим <tex>R_{i+1}</tex> через <tex>R_i</tex>:  <tex>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\}</tex>.
 
Определим <tex>R_{i+1}</tex> через <tex>R_i</tex>:  <tex>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\}</tex>.
−
 
+
Тогда: <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>.
−
Тогда: <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>
 
 
}}
 
}}
  
Строка 18: Строка 17:
 
#<tex>R_0 \subset R</tex>, где <tex>R_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} ... \left\{c_k \right\} \right\}</tex>
 
#<tex>R_0 \subset R</tex>, где <tex>R_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} ... \left\{c_k \right\} \right\}</tex>
 
#<tex> L_1, L_2 \in R \Rightarrow L_1 \cup L_2 \in R, L_1L_2 \in R, L_1^* \in R</tex>
 
#<tex> L_1, L_2 \in R \Rightarrow L_1 \cup L_2 \in R, L_1L_2 \in R, L_1^* \in R</tex>
−
Тогда регулярным языком <tex>Reg'</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... ,c_k \right\} </tex> называется пересечение всех надрезов: <tex>Reg'=\bigcap\limits_{R - nadrez}R</tex>
+
Тогда регулярным языком <tex>Reg'</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... ,c_k \right\} </tex> называется пересечение всех надрезов: <tex>Reg'=\bigcap\limits_{R - nadrez}R</tex>.
 
}}
 
}}
  
Строка 29: Строка 28:
 
*'''<tex>Reg \subset Reg'</tex>'''
 
*'''<tex>Reg \subset Reg'</tex>'''
  
−
Будем доказывать по индукции.
+
По определению <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>.
−
 
+
Рассмотрим <tex> \forall i </tex> и <tex> \forall </tex> надрез <tex> R </tex>: <tex>R_i \subset R</tex> (следует из определения <tex>R_i</tex> и определения надреза). Это выполнимо для  любого надрезa <tex> R \Rightarrow R_i \subset Reg'</tex>. Так как это выполнено для <tex> \forall i \Rightarrow \bigcup\limits_{i=0}^{\infty}R_i \subset Reg' </tex>.
−
База индукции: из первого свойства хорошего языка получаем, что <tex>\forall A: Reg_0 \subset A</tex>. Поэтому из того, что <tex>Reg'</tex> есть пересечение всех хороших языков получаем: <tex>Reg'=\bigcap\limits_{\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>A - </tex>хорошее, получаем, что <tex>Reg_{i+1}</tex> тоже содержится в <tex>A</tex>, т.е. <tex>A - xop. \Rightarrow Reg_{i+1} \subset A</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' \subset Reg</tex>'''
  
−
По определению <tex>Reg</tex> получаем, что
+
Из  определения <tex>Reg</tex> следует, что:
−
 
 
−
# <tex> Reg_0 \subset Reg </tex>
 
  
−
# <tex> L_1, L_2 \in Reg \Rightarrow L_1 \cup L_2 \in Reg, L_1L_2 \in Reg, L_1^* \in Reg </tex>  
+
# <tex> Reg_0 \subset Reg </tex>.
 +
# <tex> L_1, L_2 \in Reg \Rightarrow \exists i </tex>, что <tex> L_1\in R_i </tex> и <tex> \exists j </tex> , что <tex> 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}</tex> <tex> \Rightarrow  L_1L_2 \in Reg, L_1 \cup L_2\in Reg, L_1^* \in Reg </tex>.
  
−
Значит <tex>Reg - </tex>хорошее множество. А так как <tex>Reg'=\bigcap\limits_{\text{A- xop.}}A</tex>, то <tex>Reg' \subset Reg</tex>.
+
Значит <tex>Reg - </tex> надрез. А так как <tex>Reg'=\bigcap\limits_{\text{R- nadrez}}R</tex>, то <tex>Reg' \subset Reg</tex>.
  
 
Таким образом, теорема доказана.
 
Таким образом, теорема доказана.
 
}}
 
}}

Версия 11:11, 4 ноября 2011

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

Определение:
Регулярный язык [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] будем называть надрезом, если:

  1. [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]
  2. [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] \forall [/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] следует, что:

  1. [math] Reg_0 \subset Reg [/math].
  2. [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]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Регулярные_языки:_два_определения_и_их_эквивалентность&oldid=12702»