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

Лемма 5.2.1.

Регулярные выражения образуют ассоциативное полукольцо с операциями , то есть для любых регулярных выражений e, f и g выполняются следующие тождества:

1. e+f = f+e;
2. e+0 = e;
3. ;
4. ;
5. p;
6. ;
7. ;
8. ;
9. ;
10. .

Равенство понимается как равенство языков, задаваемых регулярными выражениями.

Лемма 5.2.2.

Для любых регулярных выражений e и f выполняются следующие тождества:

1. e+e = e;
2. (1+e+ee+...+en-1)(en)* = e*

   для любого ;

3. (e*f)*e* = (e+f)*;
4. 1+e(fe)*f = (ef)*.

Лемма 5.2.3.

Для любых регулярных выражений e, f и g, если e = ef+g и , то e = gf*.

Упражнение 5.2.4. Упростить регулярное выражение 0*.

Упражнение 5.2.5. Упростить регулярное выражение (a+b+ab)*.

Упражнение 5.2.6. Упростить регулярное выражение (a*b)*+(b*a)*.

Упражнение 5.2.7. Упростить регулярное выражение ((b+a)*b+1)b*.

Упражнение 5.2.8. Упростить регулярное выражение ((ab+aab)*a*)*.

Упражнение 5.2.9. Упростить регулярное выражение (abbaab+abbaaba)*.

Упражнение 5.2.10. Упростить регулярное выражение (a+b)*(a(a+b)*a+b(a+b)*b).

Упражнение 5.2.11. Упростить регулярное выражение (eb*(1+c(d+ab*c)*a)b*f)*eb*c(d+ab*c)*.

Содержание раздела

---

---