Регулярный язык

В теории языков регуля́рным мно́жеством (или, регуля́рным языком) называется формальный язык, который удовлетворяет приведённым ниже свойствам. Эти простые свойства таковы, что класс регулярных множеств удобно изучать в целом и полученные результаты оказываются применимы во многих важных случаях формальных языков. То есть, понятие регулярного множества является примером математической структуры.

Определение регулярного множества

Пусть Σ — конечный алфавит. Регулярное множество R(Σ) в алфавите Σ определяется следующими рекурсивными свойствами:

№.	Свойство	Описание
1	$\empty \in R(\Sigma)$	Пустое множество является регулярным множеством в алфавите Σ
2	$\{\epsilon\} \in R(\Sigma)$	Множество, состоящее из одной лишь пустой строки является регулярным множеством в алфавите Σ
3	$\forall a \in \Sigma: \{a\} \in R(\Sigma)$	Множество, состоящее из одного любого символа алфавита Σ является регулярным множеством в алфавите Σ
4	$P \in R(\Sigma) \and Q \in R(\Sigma) \Rightarrow (P \cup Q) \in R(\Sigma)$	Если два какие-либо множества являются регулярными в алфавите Σ, то и их объединение тоже является регулярным множеством в алфавите Σ
5	$P \in R(\Sigma) \and Q \in R(\Sigma) \Rightarrow PQ \in R(\Sigma)$	Если два какие-либо множества являются регулярными в алфавите Σ, то и множество, составленное из всевозможных сцеплений пар их элементов тоже является регулярным множеством в алфавите Σ
6	$P \in R(\Sigma) \Rightarrow P^* \in R(\Sigma)$	Если какое-либо множество является регулярным в алфавите Σ, то множество всевозможных сцеплений его элементов тоже является регулярным множеством в алфавите Σ
		Ничто другое, кроме следующего из перечисленного, не является регулярным множеством в алфавите Σ

---

См. также

• Построение синтаксического анализатора на основе автоматного подхода