Регулярное множество
Материал из Википедии — свободной энциклопедии
В теории языков регуля́рным мно́жеством (или, регуля́рным языком) называется формальный язык, который удовлетворяет приведённым ниже свойствам. Эти простые свойства таковы, что класс регулярных множеств удобно изучать в целом и полученные результаты оказываются применимы во многих важных случаях формальных языков. То есть, понятие регулярного множества является примером математической структуры.
[править] Определение регулярного множества
Пусть Σ — конечный алфавит. Регулярное множество в алфавите Σ R(Σ) определяется следующими рекурсивными свойствами:
Но. | Свойство | Словами |
1 | Пустое множество является регулярным множеством в алфавите Σ | |
2 | Множество, состоящее из одной лишь пустой строки является регулярным множеством в алфавите Σ | |
3 | Множество, состоящее из одного любого символа алфавита Σ является регулярным множеством в алфавите Σ | |
4 | Если два какие-либо множества являются регулярными в алфавите Σ, то и их объединение тоже является регулярным множеством в алфавите Σ | |
5 | Если два какие-либо множества являются регулярными в алфавите Σ, то и множество, составленное из всевозможных сцеплений пар их элементов тоже является регулярным множеством в алфавите Σ | |
6 | Если какое-либо множество является регулярным в алфавите Σ, то множество всевозможных сцеплений его элементов тоже является регулярным множеством в алфавите Σ | |
7 | Ничто другое, кроме следующего из перечисленного, не является регулярным множеством в алфавите Σ |