Изменения

'''Регулярный языкМножество регулярных языков''' (англ. ''set of regular languages'') <tex> Reg \mathrm{REG}</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> {{---}} языкмножество, который которое может быть получен получено из языков, каждый из букв алфавита которых содержит единственное слово {{---}} <tex>c_i</tex> или <tex>\varepsilon</tex>, и пустого языка при помощи последовательных применений операций объединения, конкатенации или итерации замыкания Клини и никаких других, то есть:* Определим регулярные языки нулевого уровня как <tex> \mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} , \ldots, \left\{c_k \right\} \right\} </tex>.* Регулярные языки ненулевого уровня определим рекуррентным соотношением: <tex> \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\} </tex>.* Тогда <tex>\mathrm{REG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>.}} {{Определение|definition = '''Регулярное выражение''' (англ. ''regular expression'') над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> {{---}} способ порождения языка над <tex>\Sigma</tex>. Определяется рекурсивно следующим образом:

обозначим * Для любого <tex>i</tex> слово <tex>c_i</tex> является регулярным выражением, задающим язык из одного слова <tex>c_i</tex>.* <tex>R_0=\leftvarepsilon</tex> является регулярным выражением, задающим язык из одной пустой строки, а <tex>\varnothing</tex> {{---}} пустой язык.* Если <tex>\alpha_1</tex> и <tex>\varnothingalpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, то <tex>(\leftalpha_1)|(\alpha_2)</tex> {\varepsilon \right\{---}}регулярное выражение, задающее <tex>L_1 \leftbigcup L_2</tex>.* Если <tex>\{c_1 alpha_1</tex> и <tex>\right\}alpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, то <tex>(\leftalpha_1)(\alpha_2)</tex> {c_2 \right\{---}} регулярное выражение, задающее <tex>L_1L_2</tex>.* Если <tex>\ldotsalpha_1</tex> является регулярным выражением, задающим язык <tex>L_1</tex>, то <tex>(\left\alpha_1)^*</tex> {{c_k \right\---} \right\}регулярное выражение, задающее <tex>L_1^*</tex>.* Операции указаны в порядке возрастания приоритета,при этом скобки повышают приоритет аналогично арифметическим выражениям.}}

определим <tex>R_{i+1}</tex> через <tex>R_i</tex>: <tex>R_{i+1} Утверждение|statement = 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>\mathrm{R}</tex> будем называть ''надрегулярным'' множеством над алфавитом <tex> \Sigma </tex>, если:

#<tex>\mathrm{R_0 } \subset \mathrm{R}</tex>, где <tex>\mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\}, \ldots, \left\{c_k \right\} \right\}</tex>,#<tex> 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}</tex>. Тогда '''регулярным языкоммножеством регулярных языков''' <tex>Reg\mathrm{REG'} </tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... \ldots ,c_k \right\} </tex> называется пересечение всех надрегулярных множеств: <tex>Reg'=\bigcap\limits_{R - nadreg}R</tex>над этим алфавитом.

Определения 1 Классы языков [[#REG1 | <tex>\mathrm{REG}</tex>]] и 2 эквивалентны[[#REG2 | <tex>\mathrm{REG'}</tex>]] над одинаковым алфавитом совпадают.

Докажем, что <tex>Reg \subset Regmathrm{REG} \subseteq \mathrm{REG'}</tex> и <tex>Reg\mathrm{REG' } \subseteq \subset Regmathrm{REG}</tex>.

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

*'''<tex>Reg\mathrm{REG' } \subset Regsubseteq \mathrm{REG} </tex>'''Докажем, что <tex> Reg \mathrm{REG} </tex> является надрегулярным множеством. Для этого проверим, выполняются ли свойства надрегулярного множества на нём: # <tex> \mathrm{R_0 }\subset Reg subseteq \mathrm{REG} </tex> {{---}} выполнено (по определению <tex>Reg\mathrm{REG} </tex>).# Рассмотрим <tex>L_1, L_2 \in Reg\mathrm{REG} </tex>. Так как <tex>Reg \mathrm{REG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>, то найдутся такие индексы <tex> \exists i : </tex> и <tex>j</tex>, что <tex>L_1\in \mathrm{R_i }</tex> и <tex> \exists j : L_2 \in \mathrm{R_j }</tex>. Тогда из определения <tex> Reg \mathrm{REG} </tex> следует, что <tex> 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}}</tex>. Так как <tex>Reg \mathrm{REG} = \bigcup\limits_{i=0}^{\infty}R_i</tex>, то получаем, что <tex> L_1L_2 \in Reg\mathrm{REG}, L_1 \cup L_2\in Reg\mathrm{REG}, L_1^* \in Reg \mathrm{REG} </tex>. Следовательно, второе свойство также выполнено.Значит, <tex>Reg\mathrm{REG} </tex> {{---}} надрегулярное множество. А так как <tex>Reg'=\bigcap\limits_{\textmathrm{R- nadregREG'}}R</tex>является пересечением всех надрегулярных множеств, то <tex>Reg\mathrm{REG' } \subseteq \subset Regmathrm{REG} </tex>.

= Литература = См. также ==* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)[[Детерминированные конечные автоматы]] == Источники информации ==