Изменения

Регулярный язык '''Множество регулярных языков''' (англ. ''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>R_0\Sigma =\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} , \ldots, \left\{c_k \right\} </tex> {{---}} способ порождения языка над <tex>\right\}Sigma</tex>. Определяется рекурсивно следующим образом:

Определим * Для любого <tex>R_{i+1}</tex> через слово <tex>c_i</tex> является регулярным выражением, задающим язык из одного слова <tex>c_i</tex>.* <tex>R_i\varepsilon</tex>: является регулярным выражением, задающим язык из одной пустой строки, а <tex>R_\varnothing</tex> {i+1{---}} = R_i пустой язык.* Если <tex>\alpha_1</tex> и <tex>\cup alpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, то <tex>(\leftalpha_1)|(\alpha_2)</tex> {{---}} регулярное выражение, задающее <tex>L_1 \cup bigcup L_2</tex>.* Если <tex>\alpha_1</tex> и <tex>\alpha_2</tex> являются регулярными выражениями, L_1L_2, L_1^* | задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, L_2 то <tex>(\in R_i\rightalpha_1)(\alpha_2)</tex> {{---}}регулярное выражение, задающее <tex>L_1L_2</tex>.Тогда: * Если <tex>Reg = \bigcupalpha_1</tex> является регулярным выражением, задающим язык <tex>L_1</tex>, то <tex>(\limits_alpha_1)^*</tex> {i=0{---}}регулярное выражение, задающее <tex>L_1^{\infty}R_i*</tex>.* Операции указаны в порядке возрастания приоритета, при этом скобки повышают приоритет аналогично арифметическим выражениям.}} {{Утверждение|statement = По построению очевидно, что множество языков, порождаемых регулярными выражениями, совпадает со множеством регулярных языков.

Множество <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 - nadrez}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>\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} \subseteq \mathrm{R}</tex>, докажем, что <tex>\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}\right\} \subseteq \mathrm{R}</tex>. Вспоминая [[#REG1 | определение]] <tex>\mathrm{R_{i + 1}}</tex> и предположение индукции (<tex>\mathrm{R_i} \subseteq \mathrm{R}</tex>), получаем, что <tex>\mathrm{R_{i + 1}} \subseteq \mathrm{R}</tex>.Так как <tex>\mathrm{REG} \subseteq R</tex> для любого надрегулярного множества <tex>R</tex>, получаем, что <tex> \mathrm{REG} \subseteq \mathrm{REG'} </tex>.

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

Докажем, что <tex> Reg </tex> является надрезом== См. Для этого проверим, выполняются ли свойства надреза на нем: также ==* [[Детерминированные конечные автоматы]]

# <tex> R_0 \subset Reg </tex> {{---}} выполнено (следует из определения <tex> Reg </tex>).# Рассмотрим <tex> L_1, L_2 \in Reg </tex>. Так как <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex> , то <tex> \exists i </tex>, что <tex> L_1\in R_i </tex> и <tex> \exists j </tex> , что <tex> L_2 \in R_j </tex>. Тогда из определения <tex> Reg </tex>, следует, что <tex> 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>Reg Источники информации = \bigcup\limits_{i=0}^{\infty}R_i</tex>, то получаем, что <tex> L_1L_2 \in Reg, L_1 \cup L_2\in Reg, L_1^* \in Reg </tex>. Следовательно второе свойство также выполнено.

Значит, <tex>Reg<* [http:/tex> /en.wikipedia.org/wiki/Regular_language Wikipedia {{---}} надрезRegular language]* [http://en. А так как <tex>Reg'=\bigcap\limits_wikipedia.org/wiki/Regular_expression Wikipedia {\text{R- nadrez--}}R<Regular expression]* [http:/tex>, то <tex>Reg' \subset Reg</tex>ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA Википедия {{---}} Регулярный язык]* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F#.D0.92_.D1.82.D0.B5.D0.BE.D1.80.D0.B8.D0.B8_.D1.84.D0.BE.D1.80.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.8F.D0.B7.D1.8B.D0.BA.D0.BE.D0.B2 Википедия {{---}}Регулярные выражения]

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