200
правок
Изменения
→Источники информации
|id = REG1
|definition =
'''Множество регулярных языков''' (англ. ''set of regular languages'') <tex>\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>.
{{Определение
|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>.
|definition =
Пусть задан алфавит <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </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> \mathrm{REG'} </tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... \ldots ,c_k \right\} </tex> называется пересечение всех надрегулярных множествнад этим алфавитом.
}}
}}
== Ссылки См. также ==* [[Детерминированные конечные автоматы]] == Источники информации ==
* [http://en.wikipedia.org/wiki/Regular_language Wikipedia {{---}} Regular language]
* [http://en.wikipedia.org/wiki/Regular_expression Wikipedia {{---}} Regular expression]
* [http://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 Википедия {{---}} Регулярные выражения]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
