Материал: Ковригин Теория автоматов Лабораторный практикум 2012
конечный автомат. Суть алгоритма заключается в том, что при обходе синтаксического дерева для каждого из поддеревьев строится структурное представление недетерминированного конечного автомата по следующим правилам.
Пусть ri и rj – некоторые подвыражения регулярного выражения r, а N(ri) и N(rj) – соответствующие им недетерминированные конечные автоматы, которые получаются при обходе синтаксического дерева, соответствующего r. Тогда:
1. Если текущий узел ε-node, то ему соответствует недетерминированный автомат, приведенный на рис. 6.1, где i – стартовое состояние, а f – принимающее состояние.
start |
ε |
|
|
i |
f |
Рис. 6.1. Структура недетерминированного конечного автомата, соответствующего регулярному выражению r = ε
2. Если текущий узел a-node (для регулярных выражений, описывающих бинарные сигналы, 0-node или 1-node), то ему соответствует недетерминированный автомат, приведенный на рис. 6.2, где i – стартовое состояние, а f – принимающее состояние.
start |
a |
|
|
i |
f |
Рис. 6.2. Структура недетерминированного конечного автомата, соответствующего регулярному выражению r = a
81
3. Если текущий узел |-node, и его дочерним узлам соответствуют недетерминированные конечные автоматы N(v) со стартовым состоянием sv и принимающим fv и N(w) со стартовым состоянием sw и принимающим fw, тогда данному узлу соответствует недетерминированный автомат, приведенный на рис. 6.3, где i – стартовое состояние, а f – принимающее состояние.
ε |
sv |
N(v) |
fv |
ε |
|
|
|
|
|
start |
|
|
|
|
i |
|
|
|
f |
|
ε |
|
|
ε |
|
sw |
N(w) |
fw |
|
Рис. 6.3. Структура недетерминированного конечного автомата, соответствующего регулярному выражению r = v|w
4. Если текущий узел ·-node, и его дочерним узлам соответствуют недетерминированные конечные автоматы N(v) со стартовым состоянием sv и принимающим fv и N(w) со стартовым состоянием sw и принимающим fw, тогда данному узлу соответствует недетерминированный автомат, приведенный на рис. 6.4, где i – стартовое состояние, f – принимающее состояние, а состояния fv и sw сливаются в одно состояние, т.е. принимающее состояние первого операнда конкатенации становится стартовым состоянием второго операнда.
82
start
sv |
N(v) |
f /s |
N(w) |
fw |
|
v w |
|
Рис. 6.4. Структура недетерминированного конечного автомата, соответствующего регулярному выражению r = vw
5. Если текущий узел *-node, и его дочернему узлу соответствует недетерминированный конечный автомат N(v) со стартовым состоянием sv и принимающим fv, тогда данному узлу соответствует недетерминированный автомат, приведенный на рис. 6.5, где i – стартовое состояние, f – принимающее состояние.
|
|
ε |
|
|
start |
ε |
|
|
ε |
|
|
|
||
i |
sv |
N(v) |
fv |
f |
|
|
|
|
ε
Рис. 6.5. Структура недетерминированного конечного автомата, соответствующего регулярному выражению r = v*
6. Если текущий узел +-node, и его дочернему узлу соответствует недетерминированный конечный автомат N(v) со стартовым состоянием sv и принимающим fv, тогда данному узлу соответствует недетерминированный автомат, приведенный на рис. 6.6, где i – стартовое состояние, f – принимающее состояние.
83
|
|
ε |
|
|
start |
ε |
|
|
ε |
|
|
|
||
i |
sv |
N(v) |
fv |
f |
|
|
|
|
Рис. 6.6. Структура недетерминированного конечного автомата, соответствующего регулярному выражению r = v*
7. Если текущий узел ?-node, и его дочернему узлу соответствует недетерминированный конечный автомат N(v) со стартовым состоянием sv и принимающим fv, тогда данному узлу соответствует недетерминированный автомат, приведенный на рис. 6.7, где i – стартовое состояние, f – принимающее состояние.
start |
ε |
|
|
ε |
|
|
|
||
i |
sv |
N(v) |
fv |
f |
|
|
|
|
ε
Рис. 6.7. Структура недетерминированного конечного автомата, соответствующего регулярному выражению r = v*.
84
Синтезированный с помощью данного алгоритма недетерминированный конечный автомат обладает следующими полезными свойствами, с точки зрения его анализа и дальнейшего использования:
1)количество состояний не более чем в два раза превышает количество символов в записи регулярного выражения;
2)автомат имеет одно начальное и одно принимающее состояние;
3)принимающее состояние не имеет исходящих переходов;
4)начальное состояние не имеет входящих переходов;
5)для любого не принимающего состояния имеется один переход по сигналу 0 или 1, или не более двух исходящих переходов по ε.
Недетерминированный конечный автомат может быть преобразован в детерминированный, при этом следует отметить, что количество состояний детерминированного конечного автомата в общем случае может экспоненциально зависеть от количества состояний недетерминированного автомата. Для начала, введем ряд понятий, которые будем использовать при описании алгоритма:
ε-замыкание z (S ') от подмножества состояний недетерми-
нированного конечного автомата S' S – это множество состояний, достижимых из данного подмножества состояний S’ по произвольному количеству ε-переходов;
следующее a-подмножество Ma(S’) от подмножества состояний недетерминированного конечного автомата S' S – подмножество состояний, достижимых из подмножества состояний S’ по одному a-переходу (для недетерминированных конечных автоматов для анализа регулярных выражений у нас будут только a-подмножества
M0(S’) и M1(S’)).
Идея данного алгоритма сводится к последовательной замене ε-замыканий от следующих a-подмножеств, построенных, начиная со стартового состояния, одним состоянием детерминированного конечного автомата.
Рассмотрим вспомогательный алгоритм построения ε-замы- кания для подмножества состояний S’ (алгоритм 6.2).
85