Лекция 5 Регулярные выражения и регулярные грамматики

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

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

Одним из способов описания языков с использованием алгебраических конструкций является задание языков регулярными выражениями. Эти конструкции включают в себя строки символов в некотором фиксированном алфавите , скобки и символы операций +,  и *. Простейшим случаем является обозначение языка {a} регулярным выражением а. Чуть сложнее выглядит регулярное выражение, обозначающее {a, b, c}:

a + b + c,

где символ + используется для операции объединения множеств. Аналогичным образом будем использовать символы  и * для обозначения операций сцепления и итерации. Так, например, выражение (a + b  c)* обозначает язык ({a}{b}{c})*= {, a, bc, aa, abc, ... }. Заметим, что здесь использована обычная иерархия операций, т.е. предполагается, что символ  связывает операнды сильнее, чем +, а символ * – сильнее, чем оба предыдущие.

Дадим строгое определение регулярных выражений. Это определение имеет рекурсивный характер, как и большинство подобных определений в алгебре и логике.

Начнем с определения одного класса множеств, называемых регулярными множествами. Это те множества, которые могут быть получены из простейших множеств строк в фиксированном алфавите  с помощью операций объединения языков, их сцепления и итерации.

Определение 5.1.

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

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

2. Множество {} – регулярное.

3. Для любого a   множество {a} – регулярное (в алфавите ).

4. Если P и Q – регулярные множества в алфавите , то регулярными являются и множества P  Q, P Q, P*.

5. Других регулярных множеств в алфавите  нет.

Итак, множество в алфавите  регулярно тогда и только тогда, когда оно либо , либо {}, либо {a}, где a  , либо получено из этих множеств применением конечного числа операций объединения, сцепления и итерации.

Определение 5.2.

Регулярные выражения в алфавите  и обозначаемые ими регулярные множества в том же алфавите определяются рекурсивно следующим образом:

1.  – регулярное выражение, обозначающее регулярное множество .

2. e – регулярное выражение, обозначающее регулярное множество {}.

3. Если а  , то а – регулярное выражение, обозначающее регулярное множество {a}.

4. Если p и q – регулярные выражения, обозначающие регулярные множества L(p) и L(q), то (p + q) – регулярное выражение, обозначающее регулярное множество L(p)  L(q); (pq) – регулярное выражение, обозначающее множество L(p)L(q); (р)* – регулярное выражение, обозначающее множество (L(p))*.

5. Других регулярных выражений в алфавите  нет.

Учитывая наше соглашение относительно приоритетов операций +,  и *, мы будем избегать употребления избыточных скобок в регулярных выражениях. Например, запись a + ba* означает выражение (a + (b(a*))).

Пример 5.3.

Для  = {a, b, c} строка (a + bc)* (c + ) является регулярным выражением, обозначающим множество {a, bc}*{c}.

Пример 5.4.

Найти множество L(a*(a + b)).

По определению 5.2. имеем: L(a*(a + b)) = L(a*)L(a + b) = (L(a*))(L(a)  L(b)) = {, a, aa, ...}{a, b} = {a, aa, aaa, ..., b, ab, aab, ...}.

Пример 5.5.

Выражение p = (aa)*  (bb)* b обозначает множество

L(p) = {a²ⁿb^{2m + 1} n  0, m  0}.

Пример 5.6.

В алфавите  = {a, b} найти регулярное выражение p такое, что L(p) = {  *  имеет, как минимум, два соседних символа а}. В этом случае любая строка   L(p) может быть представлена в виде  = aa, где  и  – произвольные строки из *. Тогда, очевидно, можно записать: p = (a + b)*aa(a + b)*.

Определение 5.7.

Регулярные выражения p и q эквивалентны, если L(p) = L(q), т.е. если они обозначают одно и то же множество. Будем в этом случае писать p =q.

Ясно, что для каждого регулярного выражения можно построить регулярное множество, обозначаемое этим выражением. Понятно, что и для каждого регулярного множества можно найти, по крайней мере, одно регулярное выражение, обозначающее это множество. Но таких выражений для одного и того же регулярного множества существует бесконечно много. Действительно, если p – регулярное выражение в алфавите , обозначающее множество L(p), то регулярные выражения p + , (p + ) + , ((p + ) + ) + , ... будут обозначать одно и то же множество L(p).

Лемма 5.8.

Пусть p, q, r – регулярные выражения. Тогда:

1. p + q = q + p

2. * = e

3. p + (q + r) = (p + q) + r

4. p(qr) = (pq)r

5. p(q + r) = pq + pr

6. (p + q)r = pr + qr

7. pe = ep = p

8. p = p = 

9. p* = p + p*

10. (p*)* = p*

11. p + p = p

12. p +  = p.

Доказательство.

1. Пусть p и q обозначают множества L(p) и L(q) соответственно. Тогда p + q обозначает L(p)  L(q), а q + p обозначает L(q)  L(p). Но L(p)  L(q) = L(q)  L(p) по свойству операции объединения множеств, следовательно, p + q = q + p. Доказательства остальных эквивалентностей проводятся по той же схеме и оставляются читателю.