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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пофикшены определения)
(Переработка первой части доказательства (суровая такая))
Строка 27: Строка 27:
  
 
*'''<tex>Reg \subset Reg'</tex>'''
 
*'''<tex>Reg \subset Reg'</tex>'''
По определению <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>.
+
По определению <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>. Покажем, что <tex>\bigcup\limits_{i=0}^{\infty}R_i \subset R</tex>,  где <tex>R</tex> {{---}} любое надрегулярное множество. Для этого докажем по индукции по <tex>i</tex>, что <tex>R_i \subset R</tex>.
Рассмотрим любое множество <tex> R_i </tex> и любое надрегулярное множество <tex> R </tex>: <tex>R_i \subset R</tex> (следует из определения <tex>R_i</tex> и определения надрегулярного множества).
+
# База: <tex>i = 0</tex>.
Это верно для любого надрегулярного множества <tex>R</tex>, следовательно <tex> R_i \subset Reg'</tex>. Также это выполнено для любого <tex> R_i </tex>, значит <tex> \bigcup\limits_{i=0}^{\infty}R_i \subset Reg' </tex>.
+
#: <tex>R_0 \subset R</tex> по определению надрегулярного множества.
 +
# Переход: известно, что <tex>R_i \subset R</tex>, докажем, что <tex>R_{i+1} \subset R</tex>.
 +
#: По определению надрегулярного множества для любых <tex>L_1, L_2 \in R_i \subset R</tex> верны утверждения: <tex>L_1 \cup L_2 \in R, L_1L_2 \in R, L_1^* \in R</tex>. То есть: <tex>\left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in R_i\right\} \subset R</tex>. Вспоминая определение <tex>R_{i+1}</tex> и предположение индукции (<tex>R_i \subset R</tex>), получаем, что <tex>R_{i+1} \subset R</tex>.
 +
Так как <tex>Reg \subset R</tex> для любого надрегулярного множества <tex>R</tex>, получаем, что <tex> \bigcup\limits_{i=0}^{\infty}R_i \subset Reg' </tex>.
  
 
*'''<tex>Reg' \subset Reg</tex>'''
 
*'''<tex>Reg' \subset Reg</tex>'''

Версия 08:02, 21 января 2012

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

Определение:
Множество регулярных языков [math] Reg [/math] над алфавитом [math] \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} [/math] — множество языков, которое может быть получено из языков, каждый из которых содержит единственное слово — [math]c_i[/math], при помощи последовательных применений операций объединения, конкатенации или итерации и никаких других, то есть:

обозначим [math]R_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} , \ldots, \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, \ldots ,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\}, \ldots, \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 - nadreg}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]\bigcup\limits_{i=0}^{\infty}R_i \subset R[/math], где [math]R[/math] — любое надрегулярное множество. Для этого докажем по индукции по [math]i[/math], что [math]R_i \subset R[/math].

  1. База: [math]i = 0[/math].
    [math]R_0 \subset R[/math] по определению надрегулярного множества.
  2. Переход: известно, что [math]R_i \subset R[/math], докажем, что [math]R_{i+1} \subset R[/math].
    По определению надрегулярного множества для любых [math]L_1, L_2 \in R_i \subset R[/math] верны утверждения: [math]L_1 \cup L_2 \in R, L_1L_2 \in R, L_1^* \in R[/math]. То есть: [math]\left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in R_i\right\} \subset R[/math]. Вспоминая определение [math]R_{i+1}[/math] и предположение индукции ([math]R_i \subset R[/math]), получаем, что [math]R_{i+1} \subset R[/math].

Так как [math]Reg \subset R[/math] для любого надрегулярного множества [math]R[/math], получаем, что [math] \bigcup\limits_{i=0}^{\infty}R_i \subset Reg' [/math].

  • [math]Reg' \subset Reg[/math]

Докажем, что [math] Reg [/math] является надрегулярным множеством. Для этого проверим, выполняются ли свойства надрегулярного множества на нём:

  1. [math] R_0 \subset Reg [/math] — выполнено (по определению [math]Reg[/math]).
  2. Рассмотрим [math]L_1, L_2 \in Reg[/math]. Так как [math]Reg = \bigcup\limits_{i=0}^{\infty}R_i[/math], то [math] \exists i : L_1\in R_i [/math] и [math] \exists j : L_2 \in R_j [/math]. Тогда из определения [math] Reg [/math] следует, что [math] 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]Reg = \bigcup\limits_{i=0}^{\infty}R_i[/math], то получаем, что [math] 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- nadreg}}R[/math], то [math]Reg' \subset Reg[/math].
[math]\triangleleft[/math]