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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
== Регулярные языки: два определения и их эквивалентность ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 11: Строка 12:
  
 
<center> 2) <math> L_1, L_2 \in A \Rightarrow L_1 \cap L_2 \in A, L_1L_2 \in A, L_1^* \in A </math></center>
 
<center> 2) <math> L_1, L_2 \in A \Rightarrow L_1 \cap L_2 \in A, L_1L_2 \in A, L_1^* \in A </math></center>
Тогда <em>регулярным языком</em> называется <math>Reg'=\bigcup_{\text{A- хорошее}}A</math>.
+
Тогда <em>регулярным языком</em> называется <math>Reg'=\bigcap_{\text{A- хорошее}}A</math>.
 
}}
 
}}
  
Строка 20: Строка 21:
 
Докажем, что <math>Reg \subset Reg'</math> и <math>Reg' \subset Reg</math>.
 
Докажем, что <math>Reg \subset Reg'</math> и <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_0 \subset Reg'</math> по определению. Пусть <math>Reg_i \subset Reg'</math>. Тогда <math>Reg_{i+1} \subset Reg'</math> по способу построения множества <math>Reg_{i+1}</math>.
  
'''<math>Reg' \subset Reg</math>:'''
+
*'''<math>Reg' \subset Reg</math>:'''
 
по определению <math>Reg - </math>хорошее множество.
 
по определению <math>Reg - </math>хорошее множество.
 
}}
 
}}

Версия 04:43, 7 октября 2010

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

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


Определение:
Пусть [math]A=\left\{L \right\}[/math]. [math]A - [/math] хорошее, если
1) [math] Reg_0 \subset A [/math]
2) [math] 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'=\bigcap_{\text{A- хорошее}}A[/math].


Теорема:
Определения 1 и 2 эквивалентны.
Доказательство:
[math]\triangleright[/math]

Докажем, что [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_{i+1}[/math].

  • [math]Reg' \subset Reg[/math]:
по определению [math]Reg - [/math]хорошее множество.
[math]\triangleleft[/math]