Задача. По заданному регулярному выражению над алфавитом найти в тексте
наименьший префикс, содержащий слово из .
Решение. Строится регулярное выражение и для него — недетерминированный конечный автомат с -переходами. Пусть это будет автомат . Если при чтении текста построенным автоматом мы приходим в финальное состояние, то это означает, что мы прочитали префикс текста , содержащий слово из языка .
Алгоритм, моделирующий работу недетерминированного конечного автомата с -переходами на входном слове .
Оценим трудоемкость приведенного алгоритма. Пусть , тогда тело цикла
оценивается как , а тело цикла " " как и весь алгоритм имеет трудоемкость .
Анализируя алгоритм построения автомата с -переходами по регулярному выражению , легко установить следующие свойства:
с учетом скобок и символов операций;
Учитывая приведенные свойства, можем теперь оценить алгоритм, моделирующий работу автомата , величиной .
Рассмотрим теперь задачу, частную по отношению к рассмотренной выше, полагая, что вместо регулярного выражения задано одно слово-образец .
Задача. Требуется найти вхождение заданного слова-образца
в слово-текст
или установить, что такого вхождения нет.
Определение.
По данному образцу определим функцию
следующим образом: — наибольший префикс слова , являющийся суффиксом слова .
Очевидно, что .
Утверждение 4.
Для любой строки и любого символа
.
Действительно, предположим, что
и , тогда , а будет префиксом и суффиксом строки , причем , что противоречит определению .
Утверждение 5.
Пусть , тогда для любого символа
.
Действительно, по предыдущему утверждению, , поэтому значение не изменится, если от строки оставить последние символов, а именно . Построим по слову-образцу конечный автомат
где , , , а переходную функцию определим следующим образом:
Для построенного автомата, очевидно, будет справедливо следующее утверждение.
Утверждение 6.
Прочитав текст , автомат
будет находиться в состоянии .
Алгоритм вычисления функции переходов: