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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Регулярное множество»)
Перейти к: навигация, поиск

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

Определение[править | править исходный текст]

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

№. Свойство Описание
1 \varnothing \in R(\Sigma) Пустое множество является регулярным языком в алфавите Σ
2 \{\varepsilon\} \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) Если какой-либо язык является регулярным в алфавите Σ, то язык из всевозможных сцеплений его элементов тоже является регулярным в алфавите Σ

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

См. также[править | править исходный текст]