Введение в схемы, автоматы и алгоритмы



             

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


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

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

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

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

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

Введем обозначения для "степеней" языка 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*

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


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