; если p и q – произвольные регулярные выражения, обозначающие регулярные множества P и Q, то p+q (или p|q), pq, p* – регулярные выражения, обозначающие соответственно регулярные множества PÈQ, PQ, P*; ничто другое регулярным выражением и регулярным множеством не является.

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

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

Свойства регулярных выражений можно записать в виде следующих формул:

e+aa*=e+a*a=a* a+b=b+a a+(b+g)=(a+b)+g a(b+g)=ab+ag (b+g)a=ba+ga

a(bg)=(ab)g a+a=a a+a*=a* e+a*=a*+e=a* 0*=e

0a=a0=0 0+a=a+0=a ea=ae=a (a*)*=a*