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

 

 

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

 

 

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

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

 

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

 

 

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

 

 

 

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

 

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

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

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

 

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