WikiSort.ru - Не сортированное

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

Определение

Пусть ${\displaystyle \Sigma }$  — конечный алфавит. Регулярный язык ${\displaystyle R(\Sigma )}$ в алфавите ${\displaystyle \Sigma }$ определяется следующими рекурсивными свойствами:

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

Ничто другое, кроме следующего из перечисленного, не является регулярным множеством в алфавите Σ

Распознаваемое подмножество моноида

Данное понятие можно обобщить на произвольный моноид. Подмножество L моноида M называется распознаваемым над M, если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M. Семейство распознаваемых подмножеств моноида M обычно обозначается ${\displaystyle \mathrm {Rec} (M)}$ ^[1].

Так если M — свободный моноид ${\displaystyle \Sigma ^{*}}$ над алфавитом ${\displaystyle \Sigma }$ , то семейство ${\displaystyle \mathrm {Rec} \left(\Sigma ^{*}\right)}$ является просто семейством регулярных языков ${\displaystyle \mathrm {Reg} \left(\Sigma ^{*}\right)}$ .

См. также

• Свойство замкнутости регулярных языков

Примечания

Для улучшения этой статьи желательно: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Исправить статью согласно стилистическим правилам Википедии. Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Проверить достоверность указанной в статье информации.