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

Элементами регулярного множества являются цепочки символов, образованные из символов алфавита X, т.е. регулярное множество представляет собой некоторый формальный язык.

Регулярными множествами являются:

1.  - пустое множество;

2. {} – множество, состоящее из одной пустой цепочки;

3. {x} – множество, состоящее из одной цепочки, представляющей собой один символ алфавита X;

4. если А и В – произвольные регулярные множества, то множества АВ, АВ, А*, В* также являются регулярными множествами;

5. ничто другое не является регулярным множеством.

Другими словами, множество цепочек, образованных из символов алфавита Х, является регулярным тогда и только тогда, когда оно либо , либо {}, либо {х} для некоторого х Х, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.

Одним из способов задания регулярного множества является регулярное выражение.

Регулярными выражениями являются:

1. 0 – регулярное выражение, обозначающее ;

2.  - регулярное выражение, обозначающее {};

3. х - регулярное выражение, обозначающее {x};

4. если а и b – регулярные выражения, обозначающие регулярные множества А и В, то:

а+в - регулярное выражение, обозначающее множество АВ;

ав - регулярное выражение, обозначающее множество АВ;

а* - регулярное выражение, обозначающее множество А*;

в* - регулярное выражение, обозначающее множество В*.

При записи регулярных выражений можно использовать круглые скобки, как и в обычных арифметических выражениях, для указания порядка выполнения операций. Для уменьшения числа скобок используются приоритеты операций: итерация самая приоритетная; менее приоритетна конкатенация; самый низкий приоритет у объединения. При отсутствии скобок операции выполняются слева направо с учётом приоритета.

Для сокращения записи регулярного выражения можно использовать систему выражений вида:

d₁=r₁

d₂=r₂

...

d_n=r_n

где d_i - различные имена, а каждое r_i - регулярное выражение над символами Х {d₁,d₂,...,d_i-1}, т.е. символами основного алфавита и ранее определенными символами. Таким образом, для любого r_i можно построить регулярное выражение над Х, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения.

Регулярные множества и регулярные выражения весьма близки. Но они представляют собой разные сущности: регулярное множество – это множество цепочек (в общем случае бесконечное), а регулярное выражение – это формула (составленная из конечного числа символов), схематично показывающая, как может быть построено соответствующее её регулярное множество.

Пример.

Регулярные выражения r₁ и r₂ в алфавите Х={ц, ., +, -}:

r₁=((ц + (+ + -)ц)ц*. + (. + (+ + -).)ц)ц*

r₂=цц*.ц* + (+ + -)цц*.ц* + (+ + -).цц* + .цц*

Одно и то же регулярное множество может быть представлено различными регулярными выражениями, например выражениями r₁ и r₂ (см. пример). Два регулярных выражения называются эквивалентными, если они определяют одно и то же регулярное множество (выражения r₁ и r₂ - эквивалентны, r₁ = r₂ ).

Для любых регулярных выражений a, b и c справедливы равенства:

1. a+b = b+a 6. a+a* = a* 11. a+a = a

2. a+(b+c) = (a+b)+c 7. aa* = a*a 12. 0a = a0 = 0

3. a(b+c) = ab+ac 8. a(ba)* = (ab)*a 13. 0+a = a+0 = a

4. (a+b)c = ac+bc 9. (a*)* = a* 14. a = a = a

5. a(bc) = (ab)c 10. 0* =  15. +a* = a*+ = a*

Эти равенства можно доказать, проверяя равенство соответствующих множеств цепочек. Их можно использовать для преобразования, в том числе и для упрощения регулярных выражений.