В теории языков регуля́рным мно́жеством (или, регуля́рным языком) называется формальный язык, который удовлетворяет приведённым ниже свойствам:
|
| Пустое множество является регулярным множеством в алфавите Σ
|
|
| Множество, состоящее из одной лишь пустой строки является регулярным множеством в алфавите Σ
|
|
| Множество, состоящее из одного любого символа алфавита Σ является регулярным множеством в алфавите Σ
|
|
| Если два какие-либо множества являются регулярными в алфавите Σ, то и их объединение тоже является регулярным множеством в алфавите Σ
|
|
| Если два какие-либо множества являются регулярными в алфавите Σ, то и множество, составленное из всевозможных сцеплений пар их элементов тоже является регулярным множеством в алфавите Σ
|
|
| Если какое-либо множество является регулярным в алфавите Σ, то множество всевозможных сцеплений его элементов тоже является регулярным множеством в алфавите Σ
|
|
| Ничто другое, кроме следующего из перечисленного, не является регулярным множеством в алфавите Σ
|
Операции над языками:
1)L=L1UL2. L состоит из всех слов которые входят в L1 или L2
2)Конкатенация L=L1L2. L состоит из всех слов, которые входят в L1 и L2
3)Итерация L*=L U LL U LLL ….(0U1)* - все слова в алфавите {0,1} включая {e}
26.Определение источника. Построение источника для регулярного языка
Источник – это фиксированный граф G, в котором:
1) некоторые вершины названы начальными
2) Каждая стрелка графа получена буквой алфавита А или немой буквой
3) Некоторые вершины названы финальными