Конструкция Томпсона

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

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

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

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

Алгоритм

Алгоритм работает рекурсивно, разбивая выражение на составляющие его подвыражения, из которых будет построен НКА с использованием набора правил. ^[3] Точнее, из регулярного выражения $E$ полученный автомат $A$ с функцией перехода $Δ$ ^{[ необходимо разъяснение ]} соблюдает следующие свойства:

$A$ имеет ровно одно начальное состояние $q 0$ , которое недоступно ни из какого другого состояния. То есть, для любого состояния $q$ и любой буквы $a$ , не содержит $q$ $0$ . $\Дельта (q,a)$
$A$ имеет ровно одно конечное состояние $q f$ , которое не является совместно доступным из любого другого состояния. То есть, для любой буквы $a$ , . $\Delta (q_{f},a)=\emptyset$
Пусть $c$ — число конкатенаций регулярного выражения $E$ , а $s$ — число символов, не считая скобок, то есть $|$ , $*$ , $a$ и $ε$ . Тогда число состояний $A$ равно $2 s - c$ (линейно по размеру $E$ ).
Число переходов из любого состояния не превышает двух.
Так как NFA из $m$ состояний и не более $e$ переходов из каждого состояния может сопоставить строку длины $n$ за время $O (emn)$ , NFA Томпсона может выполнять сопоставление с образцом за линейное время, предполагая, что алфавит фиксированного размера. ^[4]^{[ требуется лучший источник ]}

Правила

Следующие правила изображены в соответствии с Ахо и др. (2007), ^[1] стр. 122. В дальнейшем N ( s ) и N ( t ) являются НКА подвыражений s и t соответственно.

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

На рисунке ниже показан результат построения Томпсона на (ε|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», ... }.

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

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

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

Связь с другими алгоритмами

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

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

Ссылки

На Викискладе есть медиафайлы по теме « Конструкция Томпсона (формальная теория языка)» .

^ abc Альфред Вайно Ахо ; Моника С. Лам ; Рави Сети ; Джеффри Д. Ульман (2007). "3.7.4 Построение НКА из регулярного выражения" (печать) . Компиляторы: Принципы, методы и инструменты (2-е изд.). Бостон, Массачусетс, США: Pearson Addison-Wesley. стр. 159–163. ISBN 9780321486813.
^ Louden, Kenneth C. (1997). "2.4.1 От регулярного выражения к NFA" (печать) . Конструкция компилятора: принципы и практика (3-е изд.). 20 Park Plaza Boston, MA 02116-4324, США: PWS Publishing Company. стр. 64–69. ISBN 978-0-534-93972-4.{{cite book}}: CS1 maint: местоположение ( ссылка )
↑ Кен Томпсон (июнь 1968 г.). «Техники программирования: алгоритм поиска регулярных выражений». Сообщения ACM . 11 (6): 419–422. doi : 10.1145/363347.363387 . S2CID 21260384.
^ Син, Гуанмин. «Минимизированный Томпсон NFA» (PDF) .
^ Уотсон, Брюс В. (1995). Таксономия алгоритмов построения конечных автоматов (PDF) (Технический отчет). Технологический университет Эйндховена . Отчет по вычислительной науке 93/43.
^ Р. Макнотон, Х. Ямада (март 1960). «Регулярные выражения и графы состояний для автоматов». Труды IEEE по электронным компьютерам . 9 (1): 39–47. doi :10.1109/TEC.1960.5221603.