Материал: Ковригин Теория автоматов Лабораторный практикум 2012

r? – регулярное выражение, описывающее пустой сигнал либо сигнал, принадлежащий семейству S(r).

Все перечисленные выше операции левоассоциативны и имеют разные приоритеты: операции *, +, ? имеют наивысший приоритет, операция конкатенации имеет средний приоритет и операция | имеет наименьший приоритет.

Тогда сигнал, описанный в начале данного раздела, можно представить в виде следующего регулярного выражения:

101((0|1)(0|1)(0|1))+101.

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

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

Алгоритм преобразования регулярного выражения в детерминированный конечный автомат

Синтаксическое дерево – структура данных, представляющая порядок вычисления (разбора) некоторых выражений в виде древовидной структуры. В узлах дерева находятся операции, в листьях находятся операнды для данных операций.

Если рассматривать синтаксические деревья для расширенных регулярных выражений для бинарных сигналов (введенных выше),

76

то в синтаксическом дереве могут быть следующие типы узлов и листьев:

1-node – лист, соответствующий значению сигнала ‘1’; 0-node – лист, соответствующий значению сигнала ‘0’;

*-node – узел, соответствующий операции ‘*’ (имеет одного потомка);

+-node – узел, соответствующий операции ‘+’ (имеет одного потомка);

?-node – узел, соответствующий операции ‘?’ (имеет одного потомка);

·-node – узел, соответствующий операции конкатенации (имеет двух потомков);

|-node – узел, соответствующий операции ‘|’ (имеет двух потомков).

Отметим, что для метасимволов ‘( )’ нет соответствующих типов узлов, так как они только определяют порядок выполнения операций, что определяется структурой дерева.

Следует отметить, что часто, прежде чем проводить синтез синтаксического дерева, целесообразно упростить регулярное выражение, приведя его к более компактной форме, используя следующие базовые эквивалентности:

1)r | s = s | r

2)r | (s | t) = (r | s) | t

3)r(st) = (rs)t

4)r (s | t)=rs | rt

5)(s | t)r=sr | tr

6)εr = rε = r

7)r* = (r | ε)*

8)r** = r*

9)r* = r+ | ε

10)r+ = rr* = r*r

11)r? = r | ε

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

77

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

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

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

Пусть r – анализируемое регулярное выражение. Заключим это выражение в скобки:

r:= (r)

start:=первый символ r (т.е. первая круглая скобка) end:=последний символ r (последняя круглая скобка) пока в r более одного элемента {

найти ближайшую друг к другу пару скобок ‘(‘ и ‘)’ : first:=позиция ‘(‘, last:=позиция ‘)’

Проход 1: создание узлов 1-node и 0-node:

для каждого элемента в диапазоне от first до last { если элемент – символ ‘1’ {

создать 1-node

заменить в r ‘1’ на 1-node

}

иначе {

создать 0-node

заменить в r ‘0’ на 0-node

}

}

78

Проход 2: создание узлов *-node, +-node и ?-node:

для каждой пары соседних элементов в диапазоне от first

до last {

если текущая пара элементов – node и ‘*’ { создать узел *-node

установить node потомком для элемента *-node заменить в r пару node и ‘*’ на *-node

сделать *-node текущим элементом

}

если текущая пара элементов – node и ‘+’ { создать узел +-node

установить node потомком для элемента +-node заменить в r пару node и ‘+’ на +-node

сделать +-node текущим элементом

}

если текущая пара элементов – node и ‘?’ { создать узел ?-node

установить node потомком для элемента ?-node заменить в r пару node и ‘?’ на ?-node

сделать ?-node текущим элементом

}

Проход 3: создание узлов ·-node:

для каждого элемента в диапазоне от first до last { если текущий элемент – node и следующий – node {

создать узел ·-node

установить текущий node и следующий node потомками для элемента ·-node

заменить в r пару node и node на ·-node сделать ·-node текущим элементом

}

}

Проход 4: создание узлов |-node:

для каждого элемента в диапазоне от first до last {

если текущая триада соответствует node, ‘|’ и node { создать узел |-node

установить элементы node и node потомками для элемента |-node

заменить в r триаду node, ‘|’ и node на |-node

79

сделать |-node текущим элементом

}

}

Проход 5: между first (‘(‘) и last (‘)’) один элемент node: заменить в r триаду ‘(‘, node и ‘)’ на node

}

root:=node

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

Недетерминированный конечный автомат состоит из множества состояний S, одно из которых является начальным s0, множества входных символов Σ, при этом , на которых определена функция перехода f (si , a) S`,a { }, si S, S ' S и

определено множество принимающих (допускающих, или финальных) состояний F S .

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

Рассмотрим модифицированный алгоритм МакНортона– Ямады–Томпсона для преобразования регулярного выражения, описывающего бинарные сигналы, в недетерминированный

80