Построение по НКА эквивалентного ДКА, алгоритм Томпсона
Построение эквивалентного ДКА по НКА
Пусть нам дан произвольный НКА:
.Построим по нему следующий ДКА:
, где:- ,
- ,
- ,
- .
Доказательство эквивалентности
Теорема: |
Построенный ДКА эквивалентен данному НКА. |
Доказательство: |
|
Алгоритм Томпсона
Данный алгоритм преобразовывает НКА в эквивалентный ДКА. Будем использовать вышеуказанный способ построения с одним дополнением — не будем учитывать состояния недостижимые из стартового. Поэтому в алгоритме используется обход в ширину.
Алгоритм
— очередь состояний, соответствующих множествам, состоящих из состояний НКА. — стартовое состояние НКА.
.push({ }) while not isEmpty( ) .pop( ) for = for = if ( haven't been in ) .push( )
Асимптотика
Так как количество подмножеств множества состояний НКА не более, чем
, а каждое подмножество мы обрабатываем ровно один раз за время , получаем верхнюю оценку времени работы алгоритма — .Пример
Пусть нам дан исходный автомат .
По нашему заданию эквивалентного ДКА мы получаем .
- Поместим в очередь множество из одной стартовой вершины - :
- Вытащили из очереди множество :
- , положили множество в очередь:
- , нам не надо класть множество в очередь, т.к. оно уже там было
- Вытащили из очереди множество :
- , нам не надо класть множество в очередь, т.к. оно уже там было
- , нам не надо класть множество в очередь, т.к. оно уже там было