Алгебраические законы регулярных выражений

Определение. Два РВ являются эквивалентными, если при подстановке любых языков вместо переменных оба выражения представляют один и тот же язык.

Построение РВ

Алгебра РВ строится по той же схеме, что обычная арифметическая алгебра: используются константы и переменные для обозначения языков и операторы для обозначения 3 операций: объединение, конкатенация и итерация.

Базис. Состоит из 3 правил:

Индукция. Состоит из 4 правил вывода:

Приоритеты операторов РВ

1. Итерация «*»

2. Конкатенация «.»

3. Объединение «+».

Например, выражение 01^*+1 группируется как (0(1^*))+1.