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

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

, ?, a

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

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

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

L1) (

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

L1, то L2

L, а если ?

L2, то L1

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

$L^0=\{ \varepsilon\},\\ L^1= L,\\ L^{i+1} = L \circ L^i\ \ \ (i=1,2,\ldots).\\$

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

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

$(L)^*=\{ \varepsilon\} \cup \{ w\ |\ (\exists k \geq 1)( w=w_1w_2\ldots w_k) \textit{ и все}\ w_i \in L\}$

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

$(L)^*= \bigcup_{i=0}^{\infty} L^i$

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

$L^+= \bigcup_{i=1}^{\infty} L^i$

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

$L\circ 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*

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

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