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


             

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


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

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

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

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

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

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

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

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