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

Разбить на страницы

Показывать лекцию целиком

До сих пор мы рассматривали два способа конечного описания формального языка: грамматики и автоматы. Третий способ, часто наиболее удобный и компактный, - регулярные выражения. В них используются символы, обозначающие итерацию, конкатенацию и объединение языков. Например, для обозначения итерации традиционно используется символ "звездочка".

Регулярные выражения находят практическое применение во многих компьютерных приложениях, таких как текстовые редакторы и интерпретаторы командной строки. В автоматических генераторах лексических анализаторов принято использовать именно регулярные выражения в качестве формализма, с помощью которого задаются классы однотипных лексем (например, класс идентификаторов, класс десятичных констант). В языках программирования Perl, Python и др. имеется встроенная поддержка регулярных выражений.

В начале лекции даются необходимые определения. Затем в разделе 5.2* приводятся некоторые тождества регулярных выражений, такие как ассоциативность конкатенации, дистрибутивность конкатенации относительно объединения и др. В разделе 5.3 доказывается, что регулярные выражения задают в точности класс автоматных языков. В разделе 5.4* формулируется теорема о классификации автоматных языков по их сложности, измеряемой звездной высотой (необходимой глубиной вложенности итераций при задании данного языка регулярным выражением).

5.1. Определение регулярного выражения

Определение 5.1.1. Регулярное выражение над алфавитом $$\Sigma$$ определяется рекурсивно следующим образом: 0 является регулярным выражением; 1 является регулярным выражением; если $$a \in \Sigma$$, то a является регулярным выражением; если e и f являются регулярными выражениями, то $$(e \replus f)$$, $$(e \redot f)$$ и $$e^*$$ тоже являются регулярными выражениями.

Для экономии скобок будем считать, что операция ^* связывает сильнее (то есть имеет более высокий приоритет), чем умножение, а умножение связывает сильнее, чем сложение. Вместо $$e \redot f$$ часто пишут просто $$e f$$.

Пример 5.1.2. Пусть $$\Sigma = \{ a , b \}$$. Тогда $$( ( a \redot b )^* \redot ( 1 \replus a ) )$$ является регулярным выражением над алфавитом $$\Sigma$$.

Определение 5.1.3. Каждое регулярное выражение e над алфавитом $$\Sigma$$ задает (denotes, represents) некоторый язык над алфавитом $$\Sigma$$ (обозначение $$\regval{e}$$ ), определяемое рекурсивно следующим образом:$$\begin{align*} \regval{a} \bydef \{ a \} ,\mathspace\text{если}\mathspace a \in \Sigma ,\\ \regval{0} \bydef \varnothing ,\\ \regval{1} \bydef \{ \varepsilon \} ,\\ \regval{e \replus f} \bydef \regval{e} \cup \regval{f} ,\\ \regval{e \redot f} \bydef \regval{e} \cdot \regval{f} ,\\ \regval{e^*} \bydef \regval{e}^* . \end{align*}$$ Заметим, что в правой части последнего выражения символом * обозначена итерация языка (см. определение 1.2.7).

Вместо $$\regval{e}$$ часто пишут просто e.

Пример 5.1.4. Пусть $$\Sigma = \{ a , b \}$$. Согласно определению$$\regval{ ( ab )^* \redot ( 1 \replus a ) } \peq \{ (ab)^n \mid n \geq 0 \} \cup \{ (ab)^n a \mid n \geq 0 \} .$$

Определение 5.1.5. Язык L называется регулярным если он задается некоторым регулярным выражением.

Определение 5.1.6. Пусть e - регулярное выражение. Тогда $$e^+ \bydef e^* e$$.

Упражнение 5.1.7. Упростить регулярное выражение ((a+bc)^*)^*

Упражнение 5.1.8. Найти праволинейную грамматику для языка ab^*a

Упражнение 5.1.9. Найти праволинейную грамматику для языка ((a+b)a)^*.

Упражнение 5.1.10. Найти полный детерминированный конечный автомат для языка (a+b)^*(aab+abaa+abb)(a+b)^*.

Упражнение 5.1.11. Найти полный детерминированный конечный автомат для языка (a+b)^*(a(b+1)abb+baa)(a+b)^*.

Упражнение 5.1.12. Найти полный детерминированный конечный автомат для языка (b+c)((ab)^*c+(ba)^*)^*.

Упражнение 5.1.13. Найти полный детерминированный конечный автомат для языка (abab)⁺(aba)^*.

Упражнение 5.1.14. Найти полный детерминированный конечный автомат для языка (c+(a+b+c)(b+a(b+c)^*a))^*(a+b+c).

5.2*. Свойства регулярных выражений

Лемма 5.2.1. Регулярные выражения образуют ассоциативное полукольцо с операциями $$( 0 , \replus , 1 , \redot )$$, то есть для любых регулярных выражений e, f и g выполняются следующие тождества:

e+f = f+e ;

e+0 = e ;

$$(e+f)+g = e+(f+g)$$ ;

$$e \redot 1 = e$$ ;

$$1 \redot e = e$$ ;

$$(e \redot f) \redot g = e \redot (f \redot g)$$ ;

$$e \redot (f \replus g) = e \redot f \replus e \redot g$$ ;

$$(f \replus g) \redot e = f \redot e \replus g \redot e$$ ;

$$e \redot 0 = 0$$ ;

$$0 \redot e = 0$$.

Равенство понимается как равенство языков, задаваемых регулярными выражениями.

Лемма 5.2.2. Для любых регулярных выражений e и f выполняются следующие тождества:

e+e = e ;

(1+e+ee+...+e^n-1)(eⁿ)^* = e^* для любого $$n \geq 1$$ ;

(e^*f)^*e^* = (e+f)^* ;

1+e(fe)^*f = (ef)^*.

Лемма 5.2.3. Для любых регулярных выражений e, f и g, если e = ef+g и $$\varepsilon \notin \regval{ f }$$, то e = gf^*.

Упражнение 5.2.4. Упростить регулярное выражение 0^*.

Упражнение 5.2.5. Упростить регулярное выражение (a+b+ab)^*.

Упражнение 5.2.6. Упростить регулярное выражение (a^*b)^*+(b^*a)^*.

Упражнение 5.2.7. Упростить регулярное выражение ((b⁺a)^*b+1)b^*.

Упражнение 5.2.8. Упростить регулярное выражение ((ab+aab)^*a^*)^*.

Упражнение 5.2.9. Упростить регулярное выражение (abbaab+abbaaba)^*.

Упражнение 5.2.10. Упростить регулярное выражение (a+b)^*(a(a+b)^*a+b(a+b)^*b).

Упражнение 5.2.11. Упростить регулярное выражение (eb^*(1+c(d+ab^*c)^*a)b^*f)^*eb^*c(d+ab^*c)^*.

5.3. Теорема Клини

Определение 5.3.1. Назовем обобщенным конечным автоматом аналог конечного автомата, где переходы помечены не словами, а регулярными выражениями. Метка пути такого автомата - произведение регулярных выражений на переходах данного пути. Слово w допускается обобщенным конечным автоматом, если оно принадлежит языку, задаваемому меткой некоторого успешного пути.

Замечание 5.3.2. Каждый конечный автомат можно преобразовать в обобщенный конечный автомат, допускающий те же слова. Для этого достаточно заменить всюду в метках переходов пустое слово на 1, а каждое непустое слово - на произведение его букв.

Замечание 5.3.3. Если к обобщенному конечному автомату добавить переход с меткой 0, то множество допускаемых этим автоматом слов не изменится.

Пример 5.3.4. Пусть $$\Sigma = \{ a , b , c \}$$. Обобщенный конечный автомат $$\lalg Q , \Sigma , \Delta , I , F \ralg$$, где Q = {1,2,3}, I = {1,2}, F = {3},$$\Delta = \{ \lp 1 , a , 2 \rp ,\ \lp 2 , b^* ba , 2 \rp ,\ \lp 2 , b^* , 3 \rp \} ,$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "2,1" _{a} \\ *=[o][F-]{2} \ar @`{+/l16mm/} [] ^{} \ar "2,2" _{b^*} \rloop{0,-1} ^{b^*ba} *=[o][F=]{3} }$$ допускает все слова в алфавите $$\Sigma$$, кроме слов, содержащих подслово aa.

Теорема 5.3.5 (теорема Клини). Язык L является регулярным тогда и только тогда, когда он является автоматным.

Доказательство. Пусть e - регулярное выражение. Индукцией по построению e легко показать, что задаваемый им язык является автоматным (см. теорему 3.1.1).

Обратно, пусть язык L распознается некоторым (недетерминированным) конечным автоматом с одним начальным состоянием и одним заключительным состоянием. Существует эквивалентный ему обобщенный конечный автомат $$\lalg Q , \Sigma , \Delta , \{ q_1 \} , \{ q_2 \} \ralg$$, где $$q_1 \neq q_2$$. Если есть несколько переходов с общим началом и общим концом (такие переходы называются параллельными ), заменим их на один переход, используя операцию +.

Устраним по очереди все состояния, кроме q₁ и q₂. При устранении состояния q нужно для каждого перехода вида $$\lp p_1 , f_1 , q \rp$$, где $$p_1 \neq q$$, и для каждого перехода вида $$\lp q , f_2 , p_2 \rp$$, где $$p_2 \neq q$$, добавить переход $$\lp p_1 , f_1 g^* f_2 , p_2 \rp$$, где регулярное выражение g - метка перехода из q в q (если нет перехода из q в q, то надо добавить переход $$\lp p_1 , f_1 f_2 , p_2 \rp$$ ), и снова всюду заменить параллельные переходы на один переход, используя операцию +.

После устранения всех состояний, кроме q₁ и q₂, получится обобщенный конечный автомат $$\lalg \{ q_1 , q_2 \} , \Sigma , \Delta' , \{ q_1 \} , \{ q_2 \} \ralg$$, где$$\Delta' = \{ \lp q_1 , e_{11} , q_1 \rp , \lp q_1 , e_{12} , q_2 \rp , \lp q_2 , e_{21} , q_1 \rp , \lp q_2 , e_{22} , q_2 \rp \} .$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{q_1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{e_{11}} \ar "1,2" <0.6mm> ^{e_{12}} *=[o][F=]{q_2} \ar "1,1" <0.6mm> ^{e_{21}} \rloop{0,1} ^{e_{22}} }$$ Очевидно, что $$L = \regval{ e_{11}^* e_{12} ( e_{22} \replus e_{21} e_{11}^* e_{12} )^* }$$.

Пример 5.3.6. Рассмотрим язык, распознаваемый конечным автоматом$$M = \lalg \{ q_1 , q_2 , q_3 , q_4 \} , \Sigma , \Delta , \{ q_1 \} , \{ q_2 \} \ralg ,$$ где $$\Sigma = \{ a , b , c \}$$ и$$\begin{multiline*} \Delta = \{ \lp q_1 , a , q_4 \rp ,\ \lp q_2 , cb , q_2 \rp ,\ \lp q_2 , bac , q_4 \rp ,\ \\ \lp q_3 , a , q_1 \rp ,\ \lp q_3 , c , q_2 \rp ,\ \lp q_3 , c , q_4 \rp ,\ \lp q_4 , \varepsilon , q_3 \rp ,\ \lp q_4 , b , q_4 \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{q_1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{a} *=[o][F-]{q_4} \ar "2,2" <0.6mm> ^{\varepsilon} \rloop{0,1} ^{b} *=[o][F=]{q_2} \rloop{0,1} ^{cb} \ar "1,2" _{bac} \\ % *=[o][F-]{q_3} \ar "1,1" ^{a} \ar "1,3" _{c} \ar "1,2" <0.6mm> ^{c} }$$ Тот же язык порождается обобщенным конечным автоматом$$M_1 \peq \lalg \{ q_1 , q_2 , q_3 , q_4 \} , \Sigma , \Delta_1 , \{ q_1 \} , \{ q_2 \} \ralg ,$$ где$$\begin{multiline*} \Delta_1 = \{ \lp q_1 , a , q_4 \rp ,\ \lp q_2 , cb , q_2 \rp ,\ \lp q_2 , bac , q_4 \rp ,\ \\ \lp q_3 , a , q_1 \rp ,\ \lp q_3 , c , q_2 \rp ,\ \lp q_3 , c , q_4 \rp ,\ \lp q_4 , 1 , q_3 \rp ,\ \lp q_4 , b , q_4 \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{q_1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{a} *=[o][F-]{q_4} \ar "2,2" <0.6mm> ^{1} \rloop{0,1} ^{b} *=[o][F=]{q_2} \rloop{0,1} ^{cb} \ar "1,2" _{bac} \\ % *=[o][F-]{q_3} \ar "1,1" ^{a} \ar "1,3" _{c} \ar "1,2" <0.6mm> ^{c} }$$ После устранения состояния q₃ получается обобщенный конечный автомат$$M_2 = \lalg \{ q_1 , q_2 , q_4 \} , \Sigma , \Delta_2 , \{ q_1 \} , \{ q_2 \} \ralg ,$$ где$$\begin{multiline*} \Delta_2 = \{ \lp q_1 , a , q_4 \rp ,\ \lp q_2 , cb , q_2 \rp ,\ \lp q_2 , bac , q_4 \rp ,\ \\ \lp q_4 , 1 \redot a , q_1 \rp ,\ \lp q_4 , 1 \redot c , q_2 \rp ,\ \lp q_4 , b \replus 1 \redot c , q_4 \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ *=[o][F-]{q_1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" <0.6mm> ^{a} *=[o][F-]{q_4} \ar "1,1" <0.6mm> ^{1 \cdot a} \ar "1,3" <0.6mm> ^{1 \cdot c} \rloop{0,1} ^{b + 1 \cdot c} *=[o][F=]{q_2} \rloop{0,1} ^{cb} \ar "1,2" <0.6mm> ^{bac} }$$ Можно упростить регулярные выражения и получить$$\begin{multiline*} \Delta_2' = \{ \lp q_1 , a , q_4 \rp ,\ \lp q_2 , cb , q_2 \rp ,\ \lp q_2 , bac , q_4 \rp ,\ \\ \lp q_4 , a , q_1 \rp ,\ \lp q_4 , c , q_2 \rp ,\ \lp q_4 , b \replus c , q_4 \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ *=[o][F-]{q_1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" <0.6mm> ^{a} *=[o][F-]{q_4} \ar "1,1" <0.6mm> ^{a} \ar "1,3" <0.6mm> ^{c} \rloop{0,1} ^{b + c} *=[o][F=]{q_2} \rloop{0,1} ^{cb} \ar "1,2" <0.6mm> ^{bac} }$$ После устранения состояния q₄ и упрощения регулярных выражений получается обобщенный конечный автомат$$M_3 = \lalg \{ q_1 , q_2 \} , \Sigma , \Delta_3 , \{ q_1 \} , \{ q_2 \} \ralg ,$$ где$$\begin{multiline*} \Delta_3 = \{ \lp q_1 , a ( b \replus c )^* a , q_1 \rp ,\ \lp q_1 , a ( b \replus c )^* c , q_2 \rp ,\ \\ \lp q_2 , bac ( b \replus c )^* a , q_1 \rp ,\ \lp q_2 , cb \replus bac ( b \replus c )^* c , q_2 \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ *=[o][F-]{q_1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a (b+c)^* a} \ar "1,3" <0.6mm> ^{a (b+c)^* c} *=[o][F=]{q_2} \ar "1,1" <0.6mm> ^{bac (b+c)^* a} \rloop{0,1} ^{cb + bac (b+c)^* c} }$$ Следовательно, язык L(M) задается регулярным выражением$$\begin{multiline*} ( a ( b \replus c )^* a )^* a ( b \replus c )^* c \redot \\ \redot ( cb \replus bac ( b \replus c )^* c \replus bac ( b \replus c )^* a ( a ( b \replus c )^* a )^* a ( b \replus c )^* c )^* . \end{multiline*}$$ Упростив это регулярное выражение, получим$$L ( M ) = \regval{ a ( aa \replus b \replus c \replus c (cb)^* bac)^* c (cb)^* } .$$

Упражнение 5.3.7. Найти регулярное выражение для языка, порождаемого грамматикой$$\begin{align*} \regl{ S \tto b T } \regl{ S \tto a U } \regl{ T \tto c R } \regl{ T \tto e U } \regl{ R \tto d T } \regl{ U \tto \varepsilon }. \end{align*}$$

Упражнение 5.3.8. Найти регулярное выражение для языка $$\{ w \in \{a,b\}^* \mid ( | w |_a - | w |_b ) \Vdots 4 \}$$

Упражнение 5.3.9. Найти регулярное выражение для языка $$L_1 \cap L_2 \cap L_3$$, где L₁ = (aaab+c+d)^*, L₂ = (a^*ba^*ba^*bc+d)^*, L₃ = ((a+b)^*c(a+b)^*cd)^*

Упражнение 5.3.10 Найти регулярное выражение для дополнения языка (a+b)^*bbb(a+b)^* в алфавите {a,b}.

Упражнение 5.3.11 Найти регулярное выражение для дополнения языка (ab+ba)^*(1+a+b) в алфавите {a,b}.

Упражнение 5.3.12 Найти регулярное выражение для дополнения языка (a+b)^*(aab+abaa+abb)(a+b)^* в алфавите {a,b}.

Упражнение 5.3.13 Найти регулярное выражение для дополнения языка (aa(ab)^*bb(ab)^*)^* в алфавите {a,b}.

5.4*. Звездная высота

Определение 5.4.1. Звездная высота (star-height) регулярного выражения (обозначение sh(e) ) определяется рекурсивно следующим образом:$$\begin{align*} \starheight{a} \bydef 0 ,\\ \starheight{0} \bydef 0 ,\\ \starheight{1} \bydef 1 ,\\ \starheight{e \replus f} \bydef \max(\starheight{e} , \starheight{f}) ,\\ \starheight{e \redot f} \bydef \max(\starheight{e} , \starheight{f}) ,\\ \starheight{e^*} \bydef 1 + \starheight{e} . \end{align*}$$

Пример 5.4.2. Пусть $$\Sigma = \{ a , b , c \}$$. Тогда

sh((a^*+b^*+ab)^*+(ab^*c)^*)  = 2.

Определение 5.4.3. Звездной высотой регулярного языка L (обозначение sh(L) ) называется минимум звездных высот регулярных выражений, задающих этот язык.

Замечание 5.4.4. Регулярный язык L является конечным тогда и только тогда, когда sh(L) = 0.

Теорема 5.4.5. Пусть $$| \Sigma | \geq 2$$. Тогда для любого $$n \in \mathbb{N}$$ существует такой регулярный язык $$L \subseteq \Sigma ^*$$, что sh(L) = n.

Доказательство можно найти в книге Саломаа А. Жемчужины теории формальных языков. - М.: Мир, 1986 с.41-46.

Пример 5.4.6. Пусть $$\Sigma = \{ a , b \}$$ и$$L = \{ w \in \Sigma^* \mid ( | w |_a - | w |_b ) \divi 4 \} .$$ Тогда sh(L) = 2. Действительно, язык L задается регулярным выражением (ab+ba+(aa+bb)(ab+ba)^*(aa+bb))^* и не задается никаким регулярным выражением меньшей звездной высоты.

Замечание 5.4.7. Неизвестно, верен ли аналог теоремы 5.4.5 для обобщенных регулярных выражений, в которых, помимо итерации, конкатенации и объединения, разрешена операция дополнения.

Упражнение 5.4.8.Уменьшить звездную высоту регулярного выражения (a^*+b^*+ab)^*.

Упражнение 5.4.9.Уменьшить звездную высоту регулярного выражения (c(a^*b)^*)^*.

Упражнение 5.4.10.Уменьшить звездную высоту регулярного выражения (a(ab)^*b)^*.

Упражнение 5.4.11. Существует ли такой регулярный язык $$L \subseteq \{ a \} ^*$$, что sh(L) = 2?

Страницы: