Регулярные выражения и языки

Регулярные выражения являются достаточно удобным средством для построения "алгебраических" описаний языков. Они строятся из элементарных выражений

, ?, a

? с помощью операций объединения (+), конкатенации (?) и итерации (*). Каждому такому выражению r соответствует представляемый им язык Lr. Смысл операции объединения языков мы знаем. Определим операции конкатенации и итерации (иногда ее называют замыканием Клини).

Пусть L1 и L2 - языки в алфавите ?.

Тогда L= L1 ? L2= { w | (

L1) (

L2) (w = w1w2)}, т.е. конкатенация языков состоит из конкатенаций всех слов первого языка со всеми словами второго языка. В частности, если ?

L1, то L2

L, а если ?

L2, то L1

Введем обозначения для "степеней" языка L:

Таким образом в Li входят все слова, которые можно разбить на i подряд идущих слов из L.

Итерацию (L)* языка L образуют все слова которые можно разбить на несколько подряд идущих слов из L:

Ее можно представить с помощью степеней:

Часто удобно рассматривать "усеченную" итерацию языка, которая не содержит пустое слово, если его нет в языке:

. Это не новая операция, а просто удобное сокращение для выражения

Отметим также, что если рассматривать алфавит ?={a1, … , am} как конечный язык, состоящий из однобуквенных слов, то введенное ранее обозначение ?* для множества всех слов, включая и пустое, в алфавите ? соответствует определению итерации ?^* этого языка.

В следующей таблице приведено формальное индуктивное определение регулярных выражений над алфавитом ? и представляемых ими языков.

Выражениеr ЯзыкLr

	L =
?	L_?={?}
a ?	La={a}
Пустьr1иr2-это	Lr1иLr2-представляемые
регулярные выражения.	ими языки.
Тогда следующие выражения
являются регулярными	и представляют языки:
r=(r1+r2)	Lr=Lr1 Lr2
r=(r1circr2)	Lr=Lr1?Lr2
r=(r1)*	Lr=Lr1*

При записи регулярных выражений будем опускать знак конкатенации ? и будем считать, что операция * имеет больший приоритет, чем конкатенация и +, а конкатенация - больший приоритет, чем +. Это позволит опустить многие скобки.

Содержание Вперед