Регулярные выражения (РВ) - это очень удобная форма записи так называемых регулярных или автоматных языков. Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающих цепочки. Рассмотрим примеры таких систем:

• Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
• Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
• РВ в языках программирования.

В данной статье мы сначала ознакомимся с конечными автоматами и их видами (ДКА и НКА), и далее рассмотрим пример построения минимального ДКА по регулярному выражению.

Конечные автоматы

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

Рассмотрим пример работы примитивного КА:

Данный КА состоит из:

• ленты, представленной входной цепочкой.
• считывающее устройство.
• блок управления, который содержит список правил переходов.

Считывающее устройство может двигаться в одном направлении, как правило слева на право, тем самым считывая символы входной цепочки. За каждое такое движение оно может считать один символ. Далее, считанный символ передается блоку управлений. Блок управления изменяет состояние автомата на основе правил переходов. Если список правил переходов не содержит правила для считанного символа, то автомат «умирает».

Теперь рассмотрим, какими способами можно задать КА. Они могут задаваться в виде графов или в виде управляющих таблиц. В виде графа КА задается следующим способом:

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

В виде управляющей таблицы, так:

• состояния КА располагаются в строках таблицы.
• символы распознаваемого языка - в столбцах.
• на пересечении указывается состояние в которое можно попасть из данного состояния по данному символу.

Пример КА в виде графа и в виде управляющей таблицы будет представлен ниже.

ДКА и НКА

Основное отличие ДКА и НКА состоит в том, что ДКА в процессе работы может находится только в одном состоянии, а НКА в нескольких состояниях одновременно. В качестве примера работы НКА можно привести идею американского физика Хью Эверетта от том, что любое событие разбивает мир на несколько миров, в каждом из которых это событие закончилось по-своему. Например, в одном мире Гитлер выиграл Вторую мировую войну, в другом – Ньютон вместо физики занялся бизнесом и открытие законов классической механики пришлось отложить лет на 50. Чтобы сделать какие-то выводы из работы автомата, следует изучить все «миры». После того как вся входная цепочка будет считана, мы полагаем, что НКА допускает данную цепочку, если он завершил работу в допускающем состоянии хотя бы в одном из множества «миров». Соответственно, автомат отвергает цепочку, если он завершил работу в недопускающем состоянии в каждом «мире». ДКА же принимает цепочку, это очевидно, если после считывания всей входной цепочки он оказывается в допускающем состоянии.

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

Построение минимального ДКА по регулярному выражению

Для начала приведем список операций РВ используемый в данной статье, в порядке их приоритетности:

• итерация (замыкание Клини), с помощью символа "*"
• конкатенация задается с помощью пробела или пустой строки (например: ab)
• объединение, с помощью символа "|"

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

Xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

Нужно построить минимальный ДКА по регулярному выражению и продемонстрировать распознавание корректной и некорректной цепочки.

Для начала упростим данное РВ, используя правосторонний дистрибутивный закон конкатенации относительно объединения получаем следующее РВ:

(xy* | ab | (x | a*)) (x | y*)

Теперь строим автомат по данному РВ:

По правилу преобразования конкатенации (не будем приводить правила преобразования РВ в КА, так как они довольно очевидные), получаем следующий автомат:

По правилу преобразования объединения:

По правилу преобразования конкатенации:

И в конце применяем правило преобразования замыкания и получаем εНКА. Здесь нужно оговорится, что εНКА - это НКА, который содержит ε-переходы. В свою очередь ε-переход - это переход, при котором автомат не учитывает входную цепочку или другими словами переход по пустому символу.

Избавляемся от ε-переходов («звездочкой» обозначены конечные состояния):

В данном НКА состояния s3 и s5 эквивалентны, так как δ(s3, x) = δ(s5, x) = s1 и δ(s3, y) = δ(s5, y) = s5, s7. Переименовываем состояния s6 -> s5 и s7 -> s6:

Строим ДКА по НКА:

В данном ДКА состояния p1 и p5 эквивалентны, так как
δ(p1, x) = δ(p5, x) = p4 и δ(p1, y) = δ(p5, y) = p5. Переименовываем состояния p6 -> p5 и p7 -> p6:

Данный автомат является минимальным ДКА.

Пускай δ - функция переходов, то расширенную функцию переходов, построенную по δ, обозначим δ’, и ω - входная цепочка.

Допустим на вход подается цепочка ω = aaax, мы ожидаем, что автомат окажется в одном из допускающих состояний.

δ’(p0, ε) = p0
δ’(p0, a) = δ(δ’(p0, ε), a) = δ(p0, a) = p3
δ’(p0, aa) = δ(δ’(p0, a), a) = δ(p3, a) = p5
δ’(p0, aaa) = δ(δ’(p0, aa), a) = δ(p5, a) = p5
δ’(p0, aaax) = δ(δ’(p0, aaa), x) = δ(p5, x) = p4

P4 - допустимое конечное состояние, таким образом цепочка aaax является корректной для данного автомата.

Теперь допустим, что ω = xyyb:

δ’(p0, ε) = p0
δ’(p0, x) = δ(δ’(p0, ε), x) = δ(p0, x) = p1
δ’(p0, xy) = δ(δ’(p0, x), y) = δ(p1, y) = p1
δ’(p0, xyy) = δ(δ’(p0, xy), y) = δ(p1, y) = p1
δ’(p0, xyyb) = δ(δ’(p0, xyy), b) = δ(p1, b) = ∅

Здесь мы видим, что если подать на вход автомату символ b, когда он находится в состоянии p1, то данный автомат умрет, следовательно цепочка xyyb - некорректна.

P. S. В данной статье был рассмотрен алгоритм построение ДКА по РВ, но существуют более удобные алгоритмы, в частности для программирования, но это уже тема для другой статьи…

Описывать лексику языка удобнее в форме регулярных выражений, а распознавать язык с помощью КА. Поэтому важно уметь преобразовывать определения языка в форме регулярных выражений в определение в форме КА. Такое преобразование предложил Kennet Thompson.

Конечный автомат это пятерка (S, S, d, S 0 , F)

S - конечное множество состояний.

S - конечное множество допустимых входных сигналов.

d - функция переходов. Она отражает множество Sх(SÈ{e}) в множество состояний недетерминированного конечного автомата. Для детерминированного автомата функция переходов отражает множество SхS во множество состояний автомата. Другими словами, в зависимости от состояния и входного символа, d определяет новое состояние автомата.

S 0 - начальное состояние конечного автомата, S 0 Î S.

F - множество конечных состояний автомата, F Î S.

Работа конечного автомата представляет собой последовательность шагов. Шаг определяется состоянием автомата и входным символом. Сам шаг состоит в изменении состояния автомата и считывании следующего символа входной последовательности.

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

1 Регулярное выражение “e” преобразуется в автомат из двух состояний и e -перехода между ними (рисунок 1).

Рисунок 1. – Автомат для e-перехода

2 Регулярное выражение из одного символа “а” преобразуется в конечный автомат из двух состояний и перехода между ними по входному сигналу а (рисунок 2).

Рисунок 2. – Автомат для перехода по символу а

3 Пусть есть регулярное выражение rs и уже построены конечные автоматы для выражения r и выражения s. Тогда два автомата соединяются последовательно. На рисунке 3 представлены исходные автоматы для языков r и s. На рисунке автомат для распознавания конкатенации этих языков.

Автомат для r Автомат для s

Рисунок 3. – Исходные автоматы

Рисунок 4. – Автомат для конкатенации языков

4 Пусть есть регулярное выражение r | s и уже построены конечные автоматы для выражения r и выражения s (рисунок 3). Тогда в результирующем автомате должна быть альтернатива выполнения одного из двух автоматов. То есть автомат для выражения r | s при автоматах для r и s с рисунка 3 имеет вид, представленный на рисунке 5.

Рисунок 5. – Автомат для объединения языков

5 Пусть есть регулярное выражение r* при построенном конечном автомате r. В этом случае вводятся два новых состояния для возможности обхода автомата выражения r, а также вводится e-переход между конечным и начальным состояниями для возможности многократного повторения автомата r. Если для регулярного выражения r построен автомат аналогичный рисунку 3, то регулярному выражению r* соответствует конечный автомат, представленный на рисунке 6.

Регулярные выражения (РВ) - это очень удобная форма записи так называемых регулярных или автоматных языков. Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающие цепочки. Рассмотрим примеры таких систем:

• Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
• Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
• РВ в языках программирования.

В данной статье мы сначала ознакомимся с конечными автоматами и их видами(ДКА и НКА), и далее рассмотрим пример построения минимального ДКА по регулярному выражению.

Конечные автоматы

Конечный автомат (КА) - это преобразователь, который позволяет сопоставить входу соответствующий выход, причем выход этот может зависеть не только от текущего входа, но и от того, что происходило раньше, от предыстории работы конечного автомата. Даже поведение человека, а не только искусственных систем можно описать с помощью КА. С помощью КА можно описать не только поведение искусственных систем, а даже поведение человека. Например, ваша реакция, на то что ваш сосед слушает громко музыку по ночам, будет одной после первого такого случая и совершенно другой после нескольких таких случаев. Таких предысторий может быть бесконечное число, возникает вопрос; Какой памятью должен обладать КА, чтобы вести себя по разному для каждой предыстроии? Понятно, что хранить бесконечное число предысторий не возможно. Поэтому автомат как бы разбивает все возможные предыстории на классы эквивалентности. Две истории являются эквивалентными, если они одинаково влияют на поведение автомата в дальнейшем. Класс эквивалентности к которому автомат отнес свою текущую предысторию, называют еще внутренним состоянием автомата.

Теперь рассмотрим, какими способами можно задать КА. Они могут задаваться в виде графов или в виде управляющих таблиц. В виде графа КА задается следующим способом:

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

В виде управляющей таблицы, так:

• состояния КА располагаются в строках таблицы.
• символы распознаваемого языка - в столбцах.
• на пересечении указывается состояние в которое можно попасть из данного состояния по данному символу.

Пример КА в виде графа и в виде управляющей таблицы будет представлен ниже.

ДКА и НКА

Основное отличие ДКА и НКА состоит в том, что ДКА в процессе работы может находится только в одном состоянии, а НКА в нескольких состояниях одновременно. В качестве примера работы НКА можно привести идею американского физика Хью Эверетта от том, что любое событие разбивает мир на несколько миров, в каждом из которых это событие закончилось по-своему. Например, в одном мире Гитлер выиграл 2-ю Мир. войну, в другом – Ньютон вместо физики занялся бизнесом и открытие законов классической механики пришлось отложить лет на 50. Чтобы сделать какие-то выводы из работы автомата, следует изучить все «миры». После того как вся входная цепочка будет считана, мы полагаем, что НКА допускает данную цепочку, если он завершил работу в допускающем состоянии хотя бы в одном из множества «миров». Соответственно, автомат отвергает цепочку, если он завершил работу в недопускающем состоянии в каждом «мире». ДКА же принимает цепочку, это очевидно, если после считывания всей входной цепочки он оказывается в допускающем состоянии.

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

Построение минимального ДКА по регулярному выражению

Для начала приведем синтаксис РВ используемый в данной статье:

• конкатенация задается с помощью пробела или пустой строки(например: ab)
• объединение, с помощью символа "|"
• итерация(замыкание Клини), с помощью символа "*"

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

xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

Нужно построить минимальный ДКА по регулярному выражению и продемонстрировать распознавание корректной и некорректной цепочки.

Для начала упростим данное РВ, используя правосторонний дистрибутивный закон конкатенации относительно объединения получаем следующее РВ:

(xy* | ab | (x | a*)) (x | y*)

Теперь строим автомат по данному РВ:

По правилу преобразования конкатенации(не будем приводить правила преобразования РВ в КА, так как они довольно очевидные), получаем следующий автомат:

По правилу преобразования объединения:

По правилу преобразования конкатенации:

И в конце применяем правило преобразования замыкания и получаем εНКА:

Избавляемся от ε-переходов («звездочкой» обозначены конечные состояния):

В данном НКА состояния s3 и s5 эквивалентны, так как δ(s3, x) = δ(s5, x) = s1 и δ(s3, y) = δ(s5, y) = s5, s7. Переименовываем состояния s6 -> s5 и s7 -> s6:

Строим ДКА по НКА:

В данном ДКА состояния p1 и p5 эквивалентны, так как
δ(p1, x) = δ(p5, x) = p4 и δ(p1, y) = δ(p5, y) = p5. Переименовываем состояния p6 -> p5 и p7 -> p6:

Данный автомат является минимальным ДКА.

Пускай δ - функция переходов, то расширенная функция переходов, построенную по δ, обозначим δ’, и ω - входная цепочка.

Допустим на вход подается цепочка ω = aaax, мы ожидаем что автомат окажется в одном из допускающих состояний.

δ’(p0, ε) = p0
δ’(p0, a) = δ(δ’(p0, ε), a) = δ(p0, a) = p3
δ’(p0, aa) = δ(δ’(p0, a), a) = δ(p3, a) = p5
δ’(p0, aaa) = δ(δ’(p0, aa), a) = δ(p5, a) = p5
δ’(p0, aaax) = δ(δ’(p0, aaa), a) = δ(p5, a) = p4

p4 - допустимое конечное состояние, таким образом цепочка aaax, является корректной для данного автомата.

Теперь допустим, что ω = xyyb:

δ’(p0, ε) = p0
δ’(p0, x) = δ(δ’(p0, ε), x) = δ(p0, x) = p1
δ’(p0, xy) = δ(δ’(p0, x), y) = δ(p1, y) = p1
δ’(p0, xyy) = δ(δ’(p0, xy), y) = δ(p1, y) = p1
δ’(p0, xyyb) = δ(δ’(p0, xyy), b) = δ(p1, b) = ∅

Здесь мы видим, что если подать на вход автомату символ b, когда он находится в состоянии p1, то данный автомат умрет, следовательно цепочка xyyb - некорректна.

P. S. В данной статье был рассмотрен алгоритм построение ДКА по РВ, но существуют более удобные алгоритмы, в частности для программирования, но это уже тема для другой статьи…

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

Алгоритм 3.1 . Построение недетерминированного конечного автомата по регулярному выражению.

Вход . Регулярное выражение r в алфавите T .

Выход . НКА M , такой что L(M) = L(r) .

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

Построение детерминированного конечного автомата по недетерминированному

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

Алгоритм 3.2 . Построение детерминированного конечного автомата по недетерминированному.

Вход . НКА M = (Q, T, D, q 0 , F) .

Выход . ДКА .

Метод . Каждое состояние результирующего ДКА - это некоторое множество состояний исходного НКА.

В алгоритме будут использоваться следующие функции: - множество состояний НКА, достижимых из состояний, входящих в R , посредством только переходов по e , то есть множество

Множество состояний НКА, в которые есть переход на входе a для состояний из R , то есть множество

Вначале Q" и D" пусты. Выполнить шаги 1-4:

(1) Определить .

(2) Добавить в Q" как непомеченное состояние

(3) Выполнить следующую процедуру:

(4) Определить .

Пример 3.6 . Результат применения алгоритма 3.2 приведен на рис. 3.10 .

Рис. 3.10.

Построение детерминированного конечного автомата по регулярному выражению

Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [?] .

Пусть дано регулярное выражение r в алфавите T . К регулярному выражению r добавим маркер конца: (r)# . Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.

Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (r)#, каждый лист которого помечен символом , а каждая внутренняя вершина помечена знаком одной из операций: (конкатенация), | (объединение), * (итерация).

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

Обойдем дерево T снизу-вверх слева-направо и вычислим четыре функции: nullable,firstpos, lastpos и followpos . Три первые функции - nullable, firstpos и lastpos - определены на узлах дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable , является множество позиций. Функция followpos вычисляется через три остальные функции.

Функция firstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках , генерируемых подвыражением с вершиной в n . Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в

Построение детерминированного конечного автомата по регулярному выражению

Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [?].

Пусть дано регулярное выражение r в алфавите T. К регулярному выражению r добавим маркер конца: (r)#. Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.

Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (r)#, каждый лист которого помечен символом , а каждая внутренняя вершина помечена знаком одной из операций: (конкатенация),| (объединение), * (итерация).

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

Обойдем дерево T снизу-вверх слева-направо и вычислим четыре функции: nullable,firstpos, lastpos и followpos. Три первые функции - nullable, firstpos и lastpos - определены на узлах дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция followpos вычисляется через три остальные функции.

Функция firstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках , генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в подцепочках , генерируемых подвыражениями с вершиной n. Для узла n, поддеревья которого (то есть деревья, у которых узел n является корнем) могут породить пустое слово, определимnullable(n)=true, а для остальных узлов nullable(n)=false.

Таблица для вычисления функций nullable, firstpos и lastpos приведена на рис. 3.11.

Пример 3.7 .На рис. 3.12 приведено cинтаксическое дерево для пополненного регулярного выражения (a|b) * abb# с результатом вычисления функций firstpos и lastpos. Слева от каждого узла расположено значение firstpos, справа от узла - значениеlastpos. Заметим, что эти функции могут быть вычислены за один обход дерева.

Если i - позиция, то followpos(i) есть множество позиций j таких, что существует некоторая строка... cd ..., входящая в язык, описываемый регулярным выражением, такая, что позиция i соответствует этому вхождению c, а позиция j - вхождениюd.

Рис. 3.11.

Рис. 3.12.

Функция followpos может быть вычислена также за один обход дерева снизу-вверх по таким двум правилам.

1. Пусть n - внутренний узел с операцией (конкатенация), u и v - его потомки. Тогда для каждой позиции i, входящей вlastpos(u), добавляем к множеству значений followpos(i) множество firstpos(v).

2. Пусть n - внутренний узел с операцией * (итерация), u - его потомок. Тогда для каждой позиции i, входящей вlastpos(u), добавляем к множеству значений followpos(i) множество firstpos(u).

Пример 3.8 . Результат вычисления функции followpos для регулярного выражения из предыдущего примера приведен на рис. 3.13.

Алгоритм 3.3 . Прямое построение ДКА по регулярному выражению.

Вход . Регулярное выражение r в алфавите T.

Выход . ДКА M = (Q, T, D, q 0 , F), такой что L(M) = L(r).

Метод . Состояния ДКА соответствуют множествам позиций.

Вначале Q и D пусты. Выполнить шаги 1-6:

(1) Построить синтаксическое дерево для пополненного регулярного выражения (r)#.