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