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

Определение 5.1.1. Регулярное выражение над алфавитом определяется рекурсивно следующим образом: 0 является регулярным выражением; 1 является регулярным выражением; если , то a является регулярным выражением; если e и f являются регулярными выражениями, то , и тоже являются регулярными выражениями.

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

Пример 5.1.2. Пусть . Тогда является регулярным выражением над алфавитом .

Определение 5.1.3. Каждое регулярное выражение e над алфавитом задает (denotes, represents) некоторый язык над алфавитом (обозначение ), определяемое рекурсивно следующим образом:

Заметим, что в правой части последнего выражения символом * обозначена итерация языка (см. определение 1.2.7).

Вместо часто пишут просто e.

Пример 5.1.4. Пусть . Согласно определению

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

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

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

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

1. e+f = f+e;

2. e+0 = e;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. .

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

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

1. e+e = e;

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

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

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

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

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

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

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

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

Пример 5.3.4. Пусть . Обобщенный конечный автомат , где Q = {1,2,3}, I = {1,2}, F = {3},

допускает все слова в алфавите , кроме слов, содержащих подслово aa.

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

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

Обратно, пусть язык L распознается некоторым (недетерминированным) конечным автоматом с одним начальным состоянием и одним заключительным состоянием. Существует эквивалентный ему обобщенный конечный автомат , где . Если есть несколько переходов с общим началом и общим концом (такие переходы называются параллельными), заменим их на один переход, используя операцию +.

Устраним по очереди все состояния, кроме q₁ и q₂. При устранении состояния q нужно для каждого перехода вида , где , и для каждого перехода вида , где , добавить переход , где регулярное выражение g - метка перехода из q в q (если нет перехода из q в q, то надо добавить переход ), и снова всюду заменить параллельные переходы на один переход, используя операцию +.

После устранения всех состояний, кроме q₁ и q₂, получится обобщенный конечный автомат , где

Очевидно, что .

Пример 5.3.6. Рассмотрим язык, распознаваемый конечным автоматом

где и

Тот же язык порождается обобщенным конечным автоматом

где

После устранения состояния q₃ получается обобщенный конечный автомат

где

Можно упростить регулярные выражения и получить

После устранения состояния q₄ и упрощения регулярных выражений получается обобщенный конечный автомат

где

Следовательно, язык L(M) задается регулярным выражением

Упростив это регулярное выражение, получим

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

Определение 5.4.1. Звездная высота (star-height) регулярного выражения (обозначение sh(e)) определяется рекурсивно следующим образом:

Пример 5.4.2. Пусть . Тогда

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

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

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

Теорема 5.4.5. Пусть . Тогда для любого существует такой регулярный язык , что sh(L) = n.

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

Пример 5.4.6. Пусть и

Тогда sh(L) = 2. Действительно, язык L задается регулярным выражением (ab+ba+(aa+bb)(ab+ba)^*(aa+bb))^* и не задается никаким регулярным выражением меньшей звездной высоты.

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

 

 

Основная цель данной лекции - доказать еще один критерий автоматности формального языка. Этот критерий можно сформулировать в терминах классов эквивалентности слов по взаимозаменяемости (однако формальные определения будут даны без использования понятия класса эквивалентности). Слова x и y считаются взаимозаменяемыми (относительно языка L), если при замене в любом слове из языка L подслова, совпадающего с x, на y снова получится слово из языка L и наоборот. В разделе 6.3 фактически доказывается, что язык L является автоматным тогда и только тогда, когда соответствующее отношение взаимозаменяемости разбивает множество всех слов рассматриваемого алфавита на конечное число классов эквивалентности.

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

Множества правых контекстов

Определение 6.1.1. Пусть и . Тогда множество правых контекстов слова y относительно языка Lопределяется следующим образом:

Пример 6.1.2. Пусть и . Тогда

1.

2. если , то ;

3. если , то ;

4. если , то .

Определение 6.1.3. Для любого состояния p полного детерминированного конечного автомата и любого слова w обозначим через такое состояние q, что существует путь из p в q с меткой w (в силу полноты и детерминированности такое состояние существует и единственно).

Лемма 6.1.4. Если язык L распознается полным детерминированным конечным автоматом , то

Доказательство. Пусть I = {s}. Введем обозначение

Определим функцию , положив f(A) равным , где y - некоторое слово, для которого выполнено условие (если существует несколько таких слов y, то можно использовать, например, первое среди них в лексикографическом порядке).

Заметим, что для любых слов u и v, если , то . Следовательно, функция f является инъективной. Но тогда .

Пример 6.1.5. Рассмотрим язык L, порождаемый полным детерминированным конечным автоматом из примера 2.6.4. Тогда

Лемма 6.1.6. Если и множество конечно, то язык L является автоматным.

Доказательство. Язык L распознается полным детерминированным конечным автоматом , где

Пример 6.1.7. Пусть . Рассмотрим автоматный язык L = a⁺b^*. Обозначим

Тогда . Язык L распознается полным детерминированным конечным автоматом , где , , ,

Теорема 6.1.8. Язык является автоматным тогда и только тогда, когда множество конечно.

Доказательство. Необходимость доказана в лемме 6.1.4, достаточность - в лемме 6.1.6.

Замечание 6.1.9. В силу леммы 6.1.4 полный детерминированный конечный автомат, построенный в доказательстве леммы 6.1.6, является минимальным (по количеству состояний) среди всех полных детерминированных конечных автоматов, распознающих заданный язык. Можно доказать, что любой минимальный полный детерминированный конечный автомат, распознающий заданный язык, изоморфен этому автомату.