Структуры данных и модели вычислений


Применение конечных автоматов в программировании - часть 3


и .

Пришли к следующей ситуации :

Вычисляем . Видим, что условие ) во внутреннем цикле выполняется. Следовательно, вычисляется новое значение ; условие опять выполнено, вычисляем новое и на этот раз условие выполняется, снова вычисляем . Наконец внутренний цикл завершается, причиной завершения является невыполнение условия и поэтому . Итак, вычислено .

Оценим трудоемкость алгоритма.

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

или

Суммируя последнее неравенство по от до , получим

Отсюда трудоемкость оценивается сверху величиной .

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

Изложенный ниже алгоритм строит переходную функцию

автомата

где , , . Предполагаем, что функция откатов уже построена.

Для слова получим автомат, заданный диаграммой, изображенной на рис. 13.4.


Рис. 13.4. 

© 2003-2007 INTUIT.ru. Все права защищены.




Начало  Назад  



Книжный магазин