Строительство Thompsons - Thompsons construction - Wikipedia

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

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

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

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

Алгоритм

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

  • А имеет ровно одно начальное состояние q0, который недоступен из любого другого состояния. То есть для любого состояния q и любое письмо а, не содержит q0.
  • А имеет ровно одно конечное состояние qж, который недоступен из любого другого штата. То есть на любую букву а, .
  • Позволять c быть числом конкатенации регулярного выражения E и разреши s быть количеством символов без скобок, т. е. |, *, а и ε. Тогда количество состояний А является 2sc (линейная по размеру 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 - состояние запуска и приема автомата соответственно.

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

q:начать преобразовывать выражение звезды Клини(0|(1(01*(00)*0)*1)*)*
б:начать преобразование выражения объединения0|(1(01*(00)*0)*1)*
а:преобразовать символ0
п:начать преобразовывать выражение звезды Клини(1(01*(00)*0)*1)*
d:начать преобразование выражения конкатенации1(01*(00)*0)*1
c:преобразовать символ1
п:начать преобразовывать выражение звезды Клини(01*(00)*0)*
ж:начать преобразование выражения конкатенации01*(00)*0
е:преобразовать символ0
час:начать преобразовывать выражение звезды Клини1*
грамм:преобразовать символ1
час:закончил преобразование выражения звезды Клини1*
л:начать преобразовывать выражение звезды Клини(00)*
j:начать преобразование выражения конкатенации00
я:преобразовать символ0
k:преобразовать символ0
j:завершено преобразование выражения конкатенации00
л:закончил преобразование выражения звезды Клини(00)*
м:преобразовать символ0
ж:завершено преобразование выражения конкатенации01*(00)*0
п:закончил преобразование выражения звезды Клини(01*(00)*0)*
о:преобразовать символ1
d:завершено преобразование выражения конкатенации1(01*(00)*0)*1
п:закончил преобразование выражения звезды Клини(1(01*(00)*0)*1)*
б:завершено преобразование выражения объединения0|(1(01*(00)*0)*1)*
q:закончил преобразование выражения звезды Клини(0|(1(01*(00)*0)*1)*)*

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

Пример DFA умножается на 3.svg

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

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

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

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

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