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

В данном параграфе рассматриваются множества цепочек над конечным словарём, которые легко описать формулами особого вида. Эти множества называются регулярными.

Пусть V1 и V2 – множества цепочек. Определим для таких множеств три операции.

1. Объединение: V1∪ V2={α |α ∈ V1 или α ∈ V2}.

2. Конкатенация (произведение): V1∙ V2={α β |α ∈ V1, β ∈ V2}. Знак операции конкатенации обычно опускается.

Пример: V1={abc, ba}, V2={b, cb}, V1∙ V2={abcb, abccb, bab, bacb}.

Обозначим Vn произведение n множеств V (V0=ε – пустая цепочка).

3. Итерация: V*=V0∪ V1∪ V2∪ …

Определение 21. Класс регулярных множеств над конечным словарём V определяется так:

1. ∅ – регулярное множество;

2. {ε } – регулярное множество;

3. ∀ a∈ V {a} – регулярное множество;

4. Если S и T – регулярные множества, то регулярны:

– объединение S∪ T;

– конкатенация ST;

– итерации S* и T*.

5. Если множество не может быть построено конечным числом применения правил 1-4, то оно нерегулярно.

Регулярные множества обладают полезным свойством – их можно очень просто описать формулами, которые называются регулярными выражениями.

Определение 22. Класс регулярных выражений над конечным словарём V определяется так:

1. ∅ и ε – регулярные выражения;

2. ∀ a∈ V a – регулярное выражение;

3. Если R1 и R2 — регулярные выражения, то регулярными выражениями являются:

– их сумма R1+R2;

– их произведение R1∙ R2;

– их итерации R1* и R2*.

4. Если выражение не построено конечным числом применения правил 1–3, то оно не является регулярным.

Знак произведения можно опускать. Для уменьшения числа скобок, как и в любой алгебре, используются приоритеты операций: итерация самая приоритетная; менее приоритетно произведение; самый низкий приоритет у сложения.

Примеры регулярных выражений: ab+ba*, aa*b+c+dab*.

Регулярные множества и регулярные выражения весьма близки. Но они представляют собой разные сущности: регулярное множество – это множество цепочек (в общем случае бесконечное), а регулярное выражение – это формула, схематично показывающая, как было построено соответствующее ей регулярное множество с помощью перечисленных выше операций (и эта формула конечна). Таким образом, любое регулярное выражение задаёт некий язык.

Очевидно, что множество цепочек регулярно тогда и только тогда, когда оно может быть представлено регулярным выражением. Однако одно и то же множество цепочек может быть представлено различными регулярными выражениями. Если два регулярных выражения задают одно и то же регулярное множество, будем называть такие выражения эквивалентными (R1=R2). Возникает вопрос, как определить эквивалентность двух регулярных выражений.

Теорема 9. Для любых регулярных выражений R, S и T справедливо:

1. R+S=S+R; R+R=R; (R+S)+T=R+(S+T); ∅ +R=R;

2. Rε =ε R=R; (RS)T=R(ST); ∅ R=R∅ =∅; (в общем случае RS≠ SR);

3. R(S+T)=RS+RT; (S+T)R=SR+TR;

4. R*=ε +R+R2+...+Rk R*; RR*=R*R; RSR*=RS*R;

5. R+=R+R2+R3+ …; R* R+=RR*; R++ε =R*.

Эти соотношения можно доказать, проверяя равенство соответствующих множеств цепочек. Их можно использовать для упрощения регулярных выражений. Например: b(b+aa* b)=b(ε b+aa*b)=b(ε +aa*)b=ba*b.

Регулярные выражения – это конечные формулы, задающие регулярные языки. Но таким же свойством обладают и конечные автоматы – они тоже задают языки. Возникает вопрос: как соотносятся между собой классы языков, задаваемые конечными автоматами и регулярными выражениями? Стефан Клини, американский математик, доказал следующую теорему.

Теорема 10. (Теорема Клини) Классы регулярных множеств и автоматных языков совпадают.

Иными словами, каждый автоматный язык может быть задан формулой (регулярным выражением) и каждое регулярное множество может быть распознано конечным автоматом. Доказательство теоремы Клини конструктивно. На первом шаге доказывается, что для любого конечного автомата можно построить регулярное выражение, задающее распознаваемый этим автоматом язык. На втором шаге показывается, что по любому регулярному выражению можно построить конечный автомат, допускающий в точности цепочки соответствующего регулярного множества.

Покажем, что для каждого регулярного выражения R может быть построен конечный автомат AR (возможно, недетерминированный), распознающий язык, задаваемый R. Определение таких автоматов дадим рекурсивно.

1. Если R=∅, то AR= (два несвязанных состояния).

2. Если R=ε, то AR=.

3. Если R=a, то AR=.

Пусть имеется автомат AR с одним начальным и одним заключительным состоянием, допускающий язык, задаваемый R. Тогда

4. Если R=R1+R2, то

(начальные и заключительные состояния AR1 и AR2 совмещаются).

5. Если R=R1R2, то

(начальное состояние AR2 и заключительное состояние AR1 совмещаются).

6. Если R=R1*, то

Рассмотрим пример. Пусть задано выражение R=b+a+bbb+ab*a. Построим соответствующий автомат.

По правилу 4:

По правилам 4, 5 и 6:

По правилам 5 и 6:

Построенный автомат недетерминированный, с ε -переходами. После построения эквивалентного детерминированного автомата и проведения минимизации получим автомат, изображённый на рис. 17.

Рис. 17. Автомат, соответствующий b+a+bbb+ab*a.

Вопросы и упражнения.

Задайте следующие языки над словарём {0, 1} в виде регулярных выражений. Затем выполните переход от регулярного выражения к недетерминированному конечному автомату и детерминированному конечному автомату.

1. Множество цепочек, оканчивающихся на 01;

2. Множество цепочек, содержащих два нуля подряд;

3. Множество цепочек, у которых на третьей позиции справа стоит 1.

Литература

1. Карпов, Ю. Г. Теория автоматов / Ю. Г. Карпов. – СПб.: Питер, 2002. – 224 с.: ил.

2. Мозговой, М. В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход / М. В. Мозговой. – СПб.: Наука и техника, 2006. – 320 с.: ил.

3. Хопкрофт, Джон, Э. Введение в теорию автоматов, языков и вычислений, 2-е изд. / Дж. Э. Хопкрофт, Р. Мотвани, Дж. Д. Ульман; пер. с англ. – М.: Издательский дом «Вильямс», 2008. – 528 с.: ил.