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


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


Задача. По заданному регулярному выражению над алфавитом найти в тексте

наименьший префикс, содержащий слово из .

Решение. Строится регулярное выражение и для него — недетерминированный конечный автомат с -переходами. Пусть это будет автомат . Если при чтении текста построенным автоматом мы приходим в финальное состояние, то это означает, что мы прочитали префикс текста , содержащий слово из языка .

Алгоритм, моделирующий работу недетерминированного конечного автомата с -переходами на входном слове .

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

оценивается как , а тело цикла " " как и весь алгоритм имеет трудоемкость .

Анализируя алгоритм построения автомата с -переходами по регулярному выражению , легко установить следующие свойства:

  • , где — длина выражения

    с учетом скобок и символов операций;

  • ;
  • ;
  • .

Учитывая приведенные свойства, можем теперь оценить алгоритм, моделирующий работу автомата , величиной .

Рассмотрим теперь задачу, частную по отношению к рассмотренной выше, полагая, что вместо регулярного выражения задано одно слово-образец .

Задача. Требуется найти вхождение заданного слова-образца

в слово-текст

или установить, что такого вхождения нет.

Определение.

По данному образцу определим функцию

следующим образом: — наибольший префикс слова , являющийся суффиксом слова .

Очевидно, что .

Утверждение 4.

Для любой строки и любого символа

.

Действительно, предположим, что

и , тогда , а будет префиксом и суффиксом строки , причем , что противоречит определению .

Утверждение 5.

Пусть , тогда для любого символа

.

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

где , , , а переходную функцию определим следующим образом:

Для построенного автомата, очевидно, будет справедливо следующее утверждение.

Утверждение 6.

Прочитав текст , автомат

будет находиться в состоянии .

Алгоритм вычисления функции переходов:




Начало  Назад  Вперед