Пример 3.1. Несколько примеров регулярных выражений и обозначаемых ими регулярных множеств:
Ясно, что для каждого регулярного множества можно найти регулярное выражение, обозначающее это множество, и наоборот. Более того, для каждого регулярного множества существует бесконечно много обозначающих его регулярных выражений.
Будем говорить, что регулярные выражения равны или эквивалентны (=), если они обозначают одно и то же регулярное множество.
Существуют алгебраические законы, позволяющие осуществлять эквивалентное преобразование регулярных выражений.
Лемма. Пусть p, q и r - регулярные выражения. Тогда справедливы следующие соотношения:
Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть
В дальнейшем будем рассматривать только регулярные выражения, не содержащие в своей записи
где di - различные имена, а каждое ri - регулярное выражение над символами
можно построить регулярное выражение над T, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения.
Пример 3.2. Несколько примеров использования имен для обозначения регулярных выражений.