Строительство Томпсона - Википедия - Thompsons construction

В Информатика, Конструкция Томпсона алгоритм, также называемый алгоритмом Макнотона-Ямады-Томпсона^[1], это метод преобразования регулярное выражение в эквивалент недетерминированный конечный автомат (NFA).^[2] Этот NFA можно использовать для строки соответствия против регулярного выражения. Этому алгоритму приписывают Кен Томпсон.

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

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

Чтобы решить, описывают ли два заданных регулярных выражения один и тот же язык, каждое из них можно преобразовать в эквивалентный минимальный детерминированный конечный автомат через конструкцию Томпсона, конструкция электростанции, и Минимизация DFA. Если и только если полученные автоматы соглашаются вплоть до переименование состояний, языки регулярных выражений согласны.

Алгоритм

Алгоритм работает рекурсивно путем разделения выражения на составляющие подвыражения, из которых NFA будет построена с использованием набора правил.^[3] Точнее из регулярного выражения E, полученный автомат А с функцией перехода δ уважает следующие свойства:

• А имеет ровно одно начальное состояние q₀, который недоступен из любого другого состояния. То есть для любого состояния q и любое письмо а, ${ Displaystyle дельта (д, а)}$ не содержит q₀.
• А имеет ровно одно конечное состояние q_ж, который недоступен из любого другого штата. То есть на любую букву а, ${ displaystyle delta (q_ {f}, a) = emptyset}$.
• Позволять c быть числом конкатенации регулярного выражения E и разреши s быть количеством символов без скобок, т. е. |, *, а и ε. Тогда количество состояний А является 2s − c (линейная по размеру E).
• Количество переходов, выходящих из любого состояния, не превышает двух.
• Поскольку NFA м государства и самое большее е переходы из каждого состояния могут соответствовать строке длины п во время О(emn), NFA Томпсона может выполнять сопоставление с образцом за линейное время, предполагая, что алфавит фиксированного размера.^{[4][нужен лучший источник ]}

Правила

Следующие правила изображены согласно Aho et al. (2007),^[1] п. 122. Далее N(s) и N(т) - НКА подвыражений s и т, соответственно.

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

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

В выражение союза s|т конвертируется в

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

В выражение конкатенации ул конвертируется в

Исходное состояние N(s) - начальное состояние всей NFA. Окончательное состояние N(s) становится начальным состоянием N(т). Окончательное состояние N(т) является конечным состоянием всей NFA.

В Клини звезда выражение s^* конвертируется в

Ε-переход связывает начальное и конечное состояние NFA с суб-NFA. N(s) между. Еще один ε-переход от внутреннего конечного к внутреннему начальному состоянию N(s) позволяет повторять выражение s по словам звездного оператора.

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

С этими правилами, используя пустое выражение и символ правила как базовые случаи, можно доказать с помощью математическая индукция что любое регулярное выражение может быть преобразовано в эквивалентную NFA.^[1]

Пример

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

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

Пример (ε | a * b) используя конструкцию Томпсона, шаг за шагом

На рисунке ниже показан результат построения Томпсона на (ε | a * b). Розовый овал соответствует а, бирюзовый овал соответствует а *зеленый овал соответствует боранжевый овал соответствует а * б, а синий овал соответствует ε.

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

NFA, полученный из регулярного выражения (0|(1(01*(00)*0)*1)*)*

В качестве примера на картинке показан результат алгоритма построения Томпсона на регулярном выражении (0|(1(01*(00)*0)*1)*)* который обозначает набор двоичных чисел, кратных 3:

{ε, «0», «00», «11», «000», «011», «110», «0000», «0011», «0110», «1001», «1100», «1111» , "00000", ...}.

Верхняя правая часть показывает логическую структуру (синтаксическое дерево) выражения с "." обозначает конкатенацию (предполагается, что арность переменной); подвыражения названы а-q для справочных целей. В левой части показан недетерминированный конечный автомат, полученный в результате алгоритма Томпсона, с Вход и выход состояние каждого подвыражения, окрашенного в пурпурный и голубойДля ясности обозначение перехода ε опущено - немаркированные переходы на самом деле являются переходами ε. Состояние входа и выхода, соответствующее корневому выражению q - состояние запуска и приема автомата соответственно.

Шаги алгоритма следующие:

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

Отношение к другим алгоритмам

Алгоритм Томпсона - один из нескольких алгоритмов построения NFA из регулярных выражений;^[5] более ранний алгоритм был предложен Макнотоном и Ямадой.^[6] Обратимся к конструкции Томпсона, Алгоритм Клини преобразует конечный автомат в регулярное выражение.

Алгоритм построения Глушкова аналогична конструкции Томпсона после удаления ε-переходов.

Рекомендации