Регулярные выражения являются достаточно удобным средством для построения "алгебраических" описаний языков. Они строятся из элементарных выражений
Пусть L1 и L2 - языки в алфавите ?.
Тогда L= L1 ? L2= { w | (
Введем обозначения для "степеней" языка L:
Таким образом в Li входят все слова, которые можно разбить на i подряд идущих слов из L.
Итерацию (L)* языка L образуют все слова которые можно разбить на несколько подряд идущих слов из L:
Ее можно представить с помощью степеней:
Часто удобно рассматривать "усеченную" итерацию языка, которая не содержит пустое слово, если его нет в языке:
Отметим также, что если рассматривать алфавит ?={a1, … , am} как конечный язык, состоящий из однобуквенных слов, то введенное ранее обозначение ?* для множества всех слов, включая и пустое, в алфавите ? соответствует определению итерации ?^* этого языка.
В следующей таблице приведено формальное индуктивное определение регулярных выражений над алфавитом ? и представляемых ими языков.
![]() | L![]() ![]() |
? | L_?={?} |
a![]() | La={a} |
Пустьr1иr2-это | Lr1иLr2-представляемые |
регулярные выражения. | ими языки. |
Тогда следующие выражения | |
являются регулярными | и представляют языки: |
r=(r1+r2) | Lr=Lr1![]() |
r=(r1circr2) | Lr=Lr1?Lr2 |
r=(r1)* | Lr=Lr1* |
При записи регулярных выражений будем опускать знак конкатенации ? и будем считать, что операция * имеет больший приоритет, чем конкатенация и +, а конкатенация - больший приоритет, чем +. Это позволит опустить многие скобки.