Математическая теория формальных языков

       

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


Лемма 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)*.



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