Алгоритм построения Глушкова - Glushkovs construction algorithm - Wikipedia

В Информатика теория - особенно формальная теория языка - в Алгоритм построения Глушкова, изобретенный Виктор Михайлович Глушков, преобразует данный регулярное выражение в эквивалент недетерминированный конечный автомат (NFA). Таким образом, он образует мост между регулярными выражениями и недетерминированными конечными автоматами: два абстрактных представления одного и того же класса формальные языки.

Регулярное выражение можно использовать для удобного описания шаблона расширенного поиска в операции «найти и заменить» обработка текста полезность. Алгоритм Глушкова можно использовать для преобразовать в NFA, которая, к тому же, мала по своей природе, поскольку количество ее состояний равно количеству символов регулярного выражения плюс один. Следовательно, NFA можно сделать детерминированной с помощью конструкция электростанции а затем быть минимизированный чтобы получить оптимальный автомат, соответствующий заданному регулярному выражению. Последний формат лучше всего подходит для исполнения на компьютере.

С другой, более теоретической точки зрения, алгоритм Глушкова является частью доказательства того, что NFA и регулярные выражения принимают одни и те же языки; это обычные языки. Обратное алгоритму Глушкова имеет вид Алгоритм Клини, который преобразует конечный автомат в регулярное выражение. Автомат, полученный конструкцией Глушкова, совпадает с автоматом, полученным Алгоритм построения Томпсона после удаления его ε-переходов.

Строительство

Учитывая регулярное выражение е, алгоритм построения Глушкова создает недетерминированный автомат, принимающий язык ${\displaystyle L(e)}$ принят е.^{[1][2]:59—61} Конструкция состоит из четырех этапов:

Шаг 1

Линеаризация выражения. Каждая буква алфавита, встречающаяся в выражении е переименовывается, так что каждая буква встречается не более одного раза в новом выражении ${\displaystyle e'}$. Конструкция Глушкова существенно опирается на то, что ${\displaystyle e'}$ представляет местный язык ${\displaystyle L(e')}$. Позволять А будь старым алфавитом и пусть B будь новым.

Шаг 2а

Вычисление множеств ${\displaystyle P(e')}$, ${\displaystyle D(e')}$, и ${\displaystyle F(e')}$. Первый, ${\displaystyle P(e')}$, это набор букв, который встречается как первая буква слова ${\displaystyle L(e')}$. Второй, ${\displaystyle D(e')}$, это набор букв, которыми можно закончить букву ${\displaystyle L(e')}$. Последний, ${\displaystyle F(e')}$, - это набор пар букв, которые могут встречаться в словах ${\displaystyle L(e')}$, т.е. это набор множителей длины два из слов ${\displaystyle L(e')}$. Эти наборы математически определены

${\displaystyle P(e')=\{x\in B\mid xB^{*}\cap L(e')\neq \emptyset \}}$,

${\displaystyle D(e')=\{y\in B\mid B^{*}y\cap L(e')\neq \emptyset \}}$,

${\displaystyle F(e')=\{u\in B^{2}\mid B^{*}uB^{*}\cap L(e')\neq \emptyset \}}$.

Они вычисляются индукцией по структуре выражения, как описано ниже.

Шаг 2b

Расчет множества ${\displaystyle \Lambda (e')}$ который содержит пустое слово, если это слово принадлежит ${\displaystyle L(e')}$, а в противном случае - пустое множество. Формально это${\displaystyle \Lambda (e')=\{\varepsilon \}\cap L(e')}$, куда ${\displaystyle \varepsilon }$ обозначает пустое слово.

Шаг 3

Расчет местный язык,^{[требуется разъяснение ]} как определено ${\displaystyle P(e')}$, ${\displaystyle D(e')}$, ${\displaystyle F(e')}$, и ${\displaystyle \Lambda (e')}$. По определению, местный язык, определяемый наборами п, D, и F это набор слов, которые начинаются с буквы п, заканчивается буквой D, а множители длины 2 принадлежат F; то есть это язык:

${\displaystyle L'=(PB^{*}\cap B^{*}D)\setminus B^{*}(B^{2}\setminus F)B^{*}}$,

потенциально с пустым словом.

Вычисление автомата для локального языка, обозначаемое этим линеаризованным выражением, формально известно как конструкция Глушкова. Построение автомата может быть выполнено с использованием классических операций построения: конкатенации, пересечения и итерации автомата.

Шаг 4

Стирая очертания, придавая каждой букве B письмо А это было.

Пример

Автомат, построенный по алгоритму Глушкова - линейная версия

Автомат, построенный по алгоритму Глушкова - окончательная версия

Учитывать^[2]:60—61 регулярное выражение${\displaystyle e=(a(ab)^{*})^{*}+(ba)^{*}}$.

1. Линеаризованная версия

   ${\displaystyle e'=(a_{1}(a_{2}b_{3})^{*})^{*}+(b_{4}a_{5})^{*}}$.

   Буквы были линеаризованы путем добавления к ним индекса.
2. Наборы п, D, и F первых букв, последних букв и множителей длины 2 для линейного выражения соответственно равны

   ${\displaystyle {\begin{aligned}P(e')&=\{a_{1},b_{4}\}\\D(e')&=\{a_{1},b_{3},a_{5}\}\\F(e')&=\{a_{1}a_{2},a_{1}a_{1},a_{2}b_{3},b_{3}a_{1},b_{3}a_{2},b_{4}a_{5},a_{5}b_{4}\}\end{aligned}}}$.

   Пустое слово принадлежит языку, поэтому ${\displaystyle \Lambda (e')=\{\varepsilon \}}$.
3. Автомат местного языка

   ${\displaystyle L'=(PB^{*}\cap B^{*}D)\setminus B^{*}(B^{2}\setminus F)B^{*}}$

   содержит начальное состояние, обозначенное 1, и состояние для каждой из пяти букв алфавита

   ${\displaystyle B=\{a_{1},a_{2},b_{3},b_{4},a_{5}\}}$.

   Происходит переход из 1 в два состояния п, переход от Икс к у за ${\displaystyle xy\in F}$, и три состояния D конечны, и таково состояние 1. Все переходы на букву у обозначить букву у.
4. Получите автомат для ${\displaystyle L(e)}$ удалив индексы.

Вычисление набора букв

Вычисление множеств п, D, F, и Λ выполняется индуктивно по регулярное выражение ${\displaystyle e'}$. Необходимо указать значения для ∅, ε (символы для пустого языка и одноэлементного языка, содержащего пустое слово), буквы и результаты операций ${\displaystyle +,\cdot ,^{*}}$.

1. За Λ, надо

   ${\displaystyle \Lambda (\emptyset )=\emptyset }$,

   ${\displaystyle \Lambda (\varepsilon )=\{\varepsilon \}}$,

   ${\displaystyle \Lambda (a)=\emptyset }$ за каждую букву а,

   ${\displaystyle \Lambda (e+f)=\Lambda (e)\cup \Lambda (f)}$,

   ${\displaystyle \Lambda (e\cdot f)=\Lambda (e)\cdot \Lambda (f)}$, и

   ${\displaystyle \Lambda (e^{*})=\{\varepsilon \}}$.

2. За п, надо
   ${\displaystyle P(\emptyset )=P(\varepsilon )=\emptyset }$,
   ${\displaystyle P(a)=\{a\}}$ за каждую букву а,
   ${\displaystyle P(e+f)=P(e)\cup P(f)}$,
   ${\displaystyle P(e\cdot f)=P(e)\cup \Lambda (e)P(f)}$, и
   ${\displaystyle P(e^{*})=P(e)}$.

   Те же формулы используются и для D, за исключением товара, где

   ${\displaystyle D(e\cdot f)=D(f)\cup D(e)\Lambda (f)}$.

3. Для набора множителей длины 2 имеем
   ${\displaystyle F(\emptyset )=F(\varepsilon )=F(a)=\emptyset }$ за каждую букву а,
   ${\displaystyle F(e+f)=F(e)\cup F(f)}$,
   ${\displaystyle F(e\cdot f)=F(e)\cup F(f)\cup D(e)P(f)}$, и
   ${\displaystyle F(e^{*})=F(e)\cup D(e)P(e)}$.

Наиболее затратными операциями являются произведения множеств для вычисления F.

Характеристики

Полученный автомат недетерминирован и имеет столько состояний, сколько букв в регулярном выражении плюс один. Кроме того, было показано^[3]:215[4] что автомат Глушкова такой же, как Автомат Томпсона при удалении ε-переходов.

Приложения и детерминированные выражения

Вычисление автомата по выражению происходит часто; он систематически использовался в функциях поиска, в частности Unix grep команда. По аналогии, XML в спецификации также используются такие конструкции; для большей эффективности регулярные выражения определенного вида, называемые детерминированные выражения, были изучены.^[4][5]

Смотрите также

• Аналитик

Примечания и ссылки

1. В.М. Глушкова (1961). «Абстрактная теория автоматов». Российские математические обзоры (на русском). 16: 1–53. Дои:10.1070 / rm1961v016n05abeh004112.
2. Жан-Эрик Пин (ноябрь 2016 г.). Математические основы теории автоматов (PDF). Париж.
3. Жак Сакарович (февраль 2003 г.). Éléments de théorie des automates. Париж: Vuibert. ISBN  978-2711748075.
4. Жак Сакарович (2009). Элементы теории автоматов. Кембридж: Издательство Кембриджского университета. ISBN  9780521844253.
5. Брюггеманн-Кляйн, Анна (1993). «Регулярные выражения в конечных автоматах». Теоретическая информатика. 12 (2): 197–213. Дои:10.1016/0304-3975(93)90287-4.

внешняя ссылка

• Единая конструкция автоматов Глушкова, Фолловера и Антимирова.

• Алгоритмы и вычисления: 14-й международный симпозиум, ISAAC