Регулярное множество

1.

Регулярное множество

2.

• В теории формальных языков
регулярным множеством (или
регулярным языком) называется
формальный язык,
удовлетворяющий свойствам,
приведенным в таблице 1, в
которой Σ - конечный алфавит, R(Σ)
- регулярное множество в
алфавите Σ.

3.

• Для каждого регулярного множества
существует, по крайней мере, одно
регулярное выражение, обозначающее это
множество. В регулярных выражениях
операция итерации имеет наивысший
приоритет, затем выполняется операция
произведения (конкатенации), наименьший
приоритет имеет операция объединения.
Лишние скобки в регулярных выражениях
можно не записывать, если это не приводит
к недоразумениям.

4.

• Регулярные выражения в алфавите Σ
обозначают регулярные множества и
определяются следующим образом:
1. Ø- пустое множество;
2. ε - множество {ε}, включающее пустую
цепочку;
3. если а ϵ Σ, то а обозначает множество {а};
4. если р ϵ Р и q ϵ Q, то (p+q) обозначает P U Q,
(pq) - обозначает PQ, (р)*— обозначает Р*;
5. ничто другое не является регулярным
выражением.

5.

Свойства регулярных выражений
• Регулярные выражения α, β и ƴ
имеют следующие алгебраические
свойства:

6.

7.

Примеры
• Приведем примеры регулярных
выражений:
• 01 обозначает множество {01};
• (0+1) обозначает множество {0,1};
• (0+1)*101 обозначает множество
всех цепочек,
• составленных из символов 0 и 1,
которые оканчиваются цепочкой 101;