Конструкция Томпсона, известная также как алгоритм МакНотона – Ямады – Томпсона — это способ преобразования регулярного выражения в эквивалентный недетерминированный конечный автомат (НКА). Этот НКА может быть использван для сопоставления строк с регулярным выражением. Алгоритм приписывается Кену Томпсону.

Регулярные выражения и недетерминированные конечные автоматы представляют собой два способа представления формальных языков. Например, утилиты используют регулярные выражения для создания сложных шаблонов поиска, тогда как НКА лучше подходят для выполнения на компьютере. Следовательно, данный алгоритм представляет практический интерес, поскольку он позволяет компилировать регулярные выражения в НКА. С теоретической точки зрения, этот алгоритм является частью доказательства того, что оба эти подхода принимают одни и те же языки, а именно регулярные языки.

НКА можно сделать детерминированным с помощью , а затем можно минимизировать для получения оптимального автомата, соответствующего заданному регулярному выражениюя. Однако НКА может также быть интерпретирован напрямую.

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

Алгоритм

Алгоритм работает рекурсивно, разбивая выражение на составляющие подвыражения, из которых потом по определённым правилам строится НКА. Точнее, полученный из регулярного выражения автомат с функциеу перехода обладает следующими свойствами: имеет в точности одно начальное состояние , которое недоступно ни из какого-либо другого состояния. То есть, для любого состояния и любой буквы входного алфавита не содержит . имеет в точности одно конечное состояниеe , то есть, для любой буквы . Пусть будет числом конкатенаций регулярного выражения и пусть будет числом символов помимо скобок, то есть , , и . Тогда количество состояний автомата равно (линейно от размера ). Количество переходов, исходящих из любого состояния, не превышает двух. Поскольку НКА с состояниями и не более чем переходами из каждого состояния может сопоставить строку длиной за время , a НКА Томпсона может выполнять сопоставление с образцом за линейное время, при условии фиксированного размера алфавита.

Правила

Следующие правила представлены согласно книге Ахо и др. (2007). Далее N() и N() обозначают НКА для подвыражений и , соответственно.

Пустое выражение ε преобразуется в

Символ a входного алфавита преобразуется в

Выражение объединения | преобразуется в

Состояние q переходит по ε либо в начальное состояние N(), либо в начальное состояние N(). Их конечные состояния становятся промежуточными состояниями всего НКА и сливаются посредством двух ε-переходов в конечное состояние НКА.

Выражение конкатенации st преобразуется в

Начальное состояние N() является начальным состоянием всего НКА. Конечное состояние N() становится начальным состоянием N(). Конечное состояние N() является конечным состоянием всего НКА.

Звезда Клини * преобразуется в

Один ε-переход соединяет начальное и конечное состояние НКА с промежуточным под-НКА N(). Другой ε-переход от внутреннего конечного к внутреннему начальному состоянию N() позволяет повторять выражение в соответствии с оператором Клина.

Выражение в скобках () преобразуется в N().

С помощью этих правил, используя правила для пустого выражения и символа в качестве базовых случаев, можно доказать структурной индукцией, что любое регулярное выражение может быть преобразовано в эквивалентный НКА.

Пример Теперь приведём два примера. Один небольшой неформальный с результатом и побольше с пошаговым применением алгоритма.

Маленький пример

Рисунок показывает результат конструкции Томпсона на выражении (ε|a*b). Фиолетовый овал соответствует a, сине-зелёный овал соответствует a*, зелёный овал соответствует b, оранжевый овал соответствует a*b, а овал сверху соответствует ε.

Приложение алгоритма

В качестве примера рисунок сверху показывает результат алгоритма Томпсона для регулярного выражения (0|(1(01*(00)*0)*1)*)*, которое определяет множество двоичных чисел, кратных 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }.

Фрагмент справа вверху показывает логическую структуру (синтаксическое дерево) выражения, где «.» означает конкатенацию (предполагается переменная кратность). Подвыражения для удобства ссылок обозначены буквами -. Левая часть показывает недетерминированный конечный автомат полученный по алгоритму Томпсона, где и состояния каждого подвыражения выкрашены соответственно. Метка ε в переходах опущена для ясности — переходы без меток на самом деле являются ε -переходами. Входное и выходное состояния, соответствующие корневому выражению , являются начальным и конечным (принимающим) состояниями автомата.

Шаги алгоритма таковы: q: начинаем преобразование выражения со звездой Клини (0|(1(01*(00)*0)*1)*)* b: начинаем преобразование выражения объединения 0|(1(01*(00)*0)*1)* a: преобразуем символ 0 p: начинаем преобразование выражения со звездой Клини (1(01*(00)*0)*1)* d: начинаем преобразование выражения конкатенации 1(01*(00)*0)*1 c: преобразуем символ 1 n: начинаем преобразование выражения со звездой Клини (01*(00)*0)* f: начинаем преобразование выражения конкатенации 01*(00)*0 e: преобразуем символ 0 h: начинаем преобразование выражения со звездой Клини 1* g: преобразуем символ 1 h: завершаем преобразование выражения со звездой Клини 1* l: начинаем преобразование выражения со звездой Клини (00)* j: начинаем преобразование выражения конкатенации 00 i: преобразуем символ 0 k: преобразуем символ 0 j: завершаем преобразование выражения конкатенации 00 l: завершаем преобразование выражения со звездой Клини (00)* m: преобразуем символ 0 f: завершаем преобразование выражения конкатенации 01*(00)*0 n: завершаем преобразование выражения со звездой Клини (01*(00)*0)* o: преобразуем символ 1 d: завершаем преобразование выражения со звездой Клини 1(01*(00)*0)*1 p: завершаем преобразование выражения со звездой Клини (1(01*(00)*0)*1)* b: завершаем преобразование выражения объединения 0|(1(01*(00)*0)*1)* q: завершаем преобразование выражения со звездой Клини (0|(1(01*(00)*0)*1)*)*

Эквивалентный минимальный детерминированный автомат показан ниже.

Связь с другими алгоритмами Алгоритм Томпсона является одним из нескольких алгоритмов построения НКА из регулярных выражений. Более ранний алгоритм предложили Мак-Наутон и Ямада. Обратный конструкции Томпсона преобразует конечный автомат в регулярное выражение.

подобен конструкции Томпсона после удаления ε-переходов.

Применение в сравнении строк

Регулярные выражения часто используются для задания шаблонов, по которым затем производится поиск. Создавая НКА с помощью конструкции Томпсона и применяя подходящий алгоритм для его исполнения, можно разработать программное обеспечение для поиска по шаблону с производительностью , где m — длина регулярного выражения, а n — длина сопоставляемой строки. Это значительно лучше, чем достигается во многих популярных реализациях языков программирования. Однако, применение ограничено чисто регулярными выражениями и не поддерживает шаблоны для нерегулярных языков, такие как обратные ссылки.

Примечания

Литература

Категория:Конечные автоматы