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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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


Определение:
Регулярное выражение над алфавитом [math] \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} [/math] — порождающая система, задающая язык над [math] \Sigma [/math]. Определяется рекурсивно следующим образом:
  • Для любого [math]i[/math] слово [math]c_i[/math] является регулярным выражением, задающим язык из одного слова [math]c_i[/math].
  • [math]\varepsilon[/math] является регулярным выражением, задающим язык из одной пустой строки.
  • Если [math]\alpha_1[/math] и [math]\alpha_2[/math] являются регулярными выражениями, задающими языки [math]L_1[/math] и [math]L_2[/math] соответственно, то [math](\alpha_1)|(\alpha_2)[/math] — регулярное выражение, задающее [math]L_1 \bigcup L_2[/math].
  • Если [math]\alpha_1[/math] и [math]\alpha_2[/math] являются регулярными выражениями, задающими языки [math]L_1[/math] и [math]L_2[/math] соответственно, то [math](\alpha_1)(\alpha_2)[/math] — регулярное выражение, задающее [math]L_1L_2[/math].
  • Если [math]\alpha_1[/math] является регулярным выражением, задающим язык [math]L_1[/math], то [math](\alpha_1)^*[/math] — регулярное выражение, задающее [math]L_1^*[/math].
  • Операции указаны в порядке возрастания приоритета, при этом скобки повышают приоритет аналогично арифметическим выражениям.


Утверждение:
По построению очевидно, что множество языков, порождаемых регулярными выражениями, совпадает со множеством регулярных языков.


Определение:
Пусть задан алфавит [math] \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} [/math].

Множество [math]\mathrm{R}[/math] будем называть надрегулярным, если:

  1. [math]\mathrm{R_0} \subset \mathrm{R}[/math], где [math]\mathrm{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 \mathrm{R} \Rightarrow L_1 \cup L_2 \in \mathrm{R}, L_1L_2 \in \mathrm{R}, L_1^* \in \mathrm{R}[/math].

Семейство всех надрегулярных множеств обозначим [math] \mathrm{REG} [/math].

Тогда множеством регулярных языков [math] \mathrm{Reg'} [/math] над алфавитом [math] \Sigma = \left\{c_1, c_2, ... ,c_k \right\} [/math] называется пересечение всех надрегулярных множеств: [math] \mathrm{Reg'}=\bigcap\limits_{\mathrm{R} \in \mathrm{REG}}\mathrm{R} [/math].


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

Докажем, что [math]\mathrm{Reg} \subseteq \mathrm{Reg'}[/math] и [math]\mathrm{Reg'} \subseteq \mathrm{Reg}[/math].

  • [math]\mathrm{Reg} \subseteq \mathrm{Reg'}[/math]

По определению [math]\mathrm{Reg} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}[/math]. Покажем, что [math]\bigcup\limits_{i=0}^{\infty}\mathrm{R_i} \subseteq \mathrm{R}[/math], где [math]\mathrm{R}[/math] — любое надрегулярное множество. Для этого докажем по индукции по [math]i[/math], что [math]\mathrm{R_i} \subseteq \mathrm{R}[/math] для любого [math]i[/math].

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

Так как [math]\mathrm{Reg} \subseteq R[/math] для любого надрегулярного множества [math]R[/math], получаем, что [math] \mathrm{Reg} \subseteq \mathrm{Reg'} [/math].

  • [math] \mathrm{Reg'} \subseteq \mathrm{Reg} [/math]

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

  1. [math] \mathrm{R_0}\subseteq \mathrm{Reg} [/math] — выполнено (по определению [math] \mathrm{Reg} [/math]).
  2. Рассмотрим [math] L_1, L_2 \in \mathrm{Reg} [/math]. Так как [math] \mathrm{Reg} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}[/math], то [math] \exists i : L_1\in \mathrm{R_i} [/math] и [math] \exists j : L_2 \in \mathrm{R_j} [/math]. Тогда из определения [math] \mathrm{Reg} [/math] следует, что [math] L_1L_2 \in \mathrm{R_{max(i, j) + 1}}, L_1 \cup L_2\in \mathrm{R_{max(i, j) + 1}}, L_1^* \in \mathrm{R_{i + 1}}[/math]. Так как [math] \mathrm{Reg} = \bigcup\limits_{i=0}^{\infty}R_i[/math], то получаем, что [math] L_1L_2 \in \mathrm{Reg}, L_1 \cup L_2\in \mathrm{Reg}, L_1^* \in \mathrm{Reg} [/math]. Следовательно, второе свойство также выполнено.
Значит, [math] \mathrm{Reg} [/math] — надрегулярное множество. А так как [math] \mathrm{Reg'}=\bigcap\limits_{\mathrm{R} \in \mathrm{REG}}\mathrm{R}[/math], то [math] \mathrm{Reg'} \subseteq \mathrm{Reg} [/math].
[math]\triangleleft[/math]