CONSCOMP (Материалы к контрольным работам), страница 5

лист е | true | 0 | 0

--------+-------------+----------------- -+--------------

лист i | false | {i} | {i}

--------+-------------+----------------- -+--------------

u | nullable(a) | firstpos(a) | lastpos(a)

/ \ | or | u | u

a b | nullable(b) | firstpos(b) | lastpos(b)

--------+-------------+----------------- -+--------------

. | nullable(a) | if nullable(a) |if nullable(b)

/ \ | and | then firstpos(a) |then lastpos(a)

| | u firstpos(b) | u lastpos(b)

a b | nullable(b) | else firstpos(a) |else lastpos(b)

--------+-------------+----------------- -+--------------

* | | |

| | true | firstpos(a) | lastpos(a)

a | | |

---------------------------------------- ----------------

Рис. 2.5

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

на рис. 2.5. Вычисление функции lastpos строится аналогично.

{1,2,3}.{6}

/ \

{1,2,3}.{5} {6}#{6}

/ \ позиция | followpos

{1,2,3}.{4} {5}b{5} --------+-------------

/ \ 1 | {1,2,3}

{1,2,3}.{3} {4}b{4} 2 | {1,2,3}

/ \ 3 | {4}

{1,2}*{1,2} {3}a{3} 4 | {5}

| 5 | {6}

{1,2}u{1,2} 6 | -

/ \ ----------------------

{1}a{1} {2}b{2}

Рис. 2.6 Рис. 2.7

Пример 2.3. Функции firstpos и lastpos для выражения (a+b)abb#

приведены на рис. 2.6. Слева от каждой вершины значение

firstpos, справа - lastpos. Заметим, что эти функции могут

быть вычислены за один обход дерева.

Если i - позиция, то followpos(i) есть множество позиций j

таких, что существует некоторая строка ...cd..., входящая в

язык, описываемый РВ, такая, что i - соответствует этому

вхождению c, а j - вхождению d.

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

дерева по следующим двум правилам

1. Пусть n - внутренний узел с операцией "." (конкатенация),

a,b - его потомки. Тогда для каждой позиции i, входящей в

lastpos(a), добавляем к множеству значений followpos(i)

множество firstpos(b).

2. Пусть n - внутренний узел с операцией "*" (итерация), a -

его потомок. Тогда для каждой позиции i, входящей в

lastpos(a), добавляем к множеству значений followpos(i)

множество firstpos(а).

Для примера 2.3 значения функции followpos приведены на рис.

2.7.

Функция followpos позволит теперь сразу построить

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

алгоритма.

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

Будем строить множество состояний автомата dstates и помечать

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

состоянием будет состояние firstpos(root), где root - вершина

синтаксического дерева регулярного выражения, конечными - все

состояния, содержащие позиции, связанные с символом "#".

Сначала в dstates имеется только одно непомеченное состояние

firstpos(root).

while есть непомеченное состояние t в dstates do

пометить t;

for каждого входного символа a<-t do

пусть символу a в t соответствуют позиции

p1,...,pi, и пусть s=u followpos(pi)

i

Если s не пусто и s не принадлежит dstates, то

добавить непомеченное состояние s в dstates

(рис. 2.8)

Функцию перехода dtran для t и a определить как

dtran(t,a)=s.

end;

end;

Для примера 2.3 вначале t={1(a),2(b),3(a)}. Последовательность

шагов алгоритма приведена на рис. 2.9. В результате будет

построен детерминированный конечный автомат, изображенный на

рис. 2.10. Состояния автомата обозначаются как множества

позиций, например {1,2,3}, конечное состояние заключено в

квадратные скобки [1,2,3,6].

a: {1,2,3,4} t={1(a),2(b),3(a)}

b: {1,2,3} / / \

v v v

{1,2,3} {4}

+------------+ +----+ a: {1,2,3,4} t={1(a),2(b),3(a),4(b)}

|+----+ | | | b: {1,2,3,5} / / | |

||b | | | | v v v v

||----+------+-+>sb | {1,2,3} {4} {5}

||{pb}|+----+| |----|

|+----+|a || | | a: {1,2,3,4} t={1(a),2(b),3(a),5(b)}

| |----++-+>sa | b: {1,2,3,6} / / | |

| |{pa}|| | | v v v v

| +----+| | | {1,2,3} {4} {6}

+------------+ +----+

a: {1,2,3,4} t={1(a),2(b),3(a),6(#)}

b: {1,2,3} / / |

v v v

{1,2,3} {4}

Рис. 2.8 Рис. 2.9

+--------------------b------------------ --+

| +-----------a--------------+ |

+-+ | +-+ | +----a-----+ | |

|b| | |a| | | | | |

v | v a v | v v b | b | |

---->{1,2,3}--->{1,2,3,4}----->{1,2,3,5} ----->[1,2,3,6]

Рис. 2.10

2.4. Построение детерминированного конечного автомата с

минимальным числом состояний

Рассмотрим теперь алгоритм построения ДКА с минимальным числом

состояний, эквивалентного данному ДКА [2].

Алгоритм 2.2. Построение ДКА с минимальным числом состояний.

Шаг 1. Строим начальное разбиение П множества состояний из

двух групп: заключительное состояние и остальные s-f.

Шаг 2. Применяем к П следующую процедуру и получаем новое

разбиение Пnew (рис. 2.11):

for каждой группы g в П do

разбиваем g на подгруппы так, чтобы

состояния s и t из g оказались в одной

группе тогда и только тогда, когда для каждого

входного символа a состояния s и t имеют

переходы по a в состояния из одной и той же

группы в П;

заменяем g в Пnew на множество всех

полученных подгрупп

end;

+---+ +-+ +-+

+-----|s,t|-----+ |s| |t|

| +---+ | +-+ +-+

|a a| | |

| +---+ | v v

+---->| |<----+ +-+ +-+

+---+ | | | |

+-+ +-+

Рис. 2.11

Шаг 3. Если Пnew=П, полагаем Пres=П и переходим к шагу 4,

иначе повторяем шаг 2 с П:=Пnew.

Шаг 4. Выберем по одному состоянию из каждой группы в

разбиении Пres в качестве представителя для этой группы.

Представители будут состояниями приведенного ДКА М'. Пусть s -

представитель. Предположим, что на входе a в m существует

переход из t. Пусть r - представитель группы t. Тогда М' имеет

переход из a в r по a. Пусть начальное состояние М' -

представитель группы, содержащей начальное состояние s0

исходного m, и пусть заключительные состояния М' -

представители в f. Отметим, что каждая группа Пres либо