Регулярные выражения. Свойства регулярных выражений

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

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

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

3. а — регулярное выражение, обозначающее {a} "aÎV.

4. Если р и q — регулярные выражения, обозначающие регулярные множества Р и Q, то p+q, pq, р* — регулярные выражения, обозначающие регулярные множества PÈQ, PQ и Р* соответственно.

Два регулярных выражения a и b равны, a = b, если они обозначают одно и то же множество.

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

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

Если a, b и g — регулярные выражения, то свойства регулярных выражений можно записать в виде следующих формул:

1. g+aa* = g+a*a = a*

2. a+b = b+a.

3. a+(b+g) = (a+b)+g

4. a(b+g) = ab+ag

5. (b+g)a = ba+ga

6. a(bg) = (ab)g

7. a+a = a

8. a+a* = a*

9. l+a* = a*+l = a*

10. 0* = l

11. 0a = a0 = 0

12. 0+a = a+0 = a

13. la = al = a

14. (a*)* = a*

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

Следует также обратить внимание на то, что среди прочих свойств отсутствует равенство ab = ba, то есть операция конкатенации не обладает свойством комму­тативности. Это и не удивительно, поскольку для этой операции важен порядок следования символов.

Предлагаю ознакомиться с аналогичными статьями: