WikiDer > Алгоритм построения Глушкова - Википедия

Glushkovs construction algorithm - Wikipedia

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

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

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

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

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

Шаг 1

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

Шаг 2а

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

{ 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 (е ')}$ который содержит пустое слово, если это слово принадлежит ${ Displaystyle L (е ')}$ , а в противном случае - пустое множество. Формально это ${ Displaystyle Lambda (е ') = { varepsilon } cap L (е')}$ , куда ${ displaystyle varepsilon}$ обозначает пустое слово.

Шаг 3

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

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

,

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

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

Шаг 4

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

Пример

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

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

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

Линеаризованная версия
${ displaystyle e '= (a_ {1} (a_ {2} b_ {3}) ^ {*}) ^ {*} + (b_ {4} a_ {5}) ^ {*}}$ .
Буквы были линеаризованы путем добавления к ним индекса.
Наборы $п$ , $D$ , и $F$ первых букв, последних букв и множителей длины 2 для линейного выражения соответственно равны
${ displaystyle { begin {align} 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 {align}}}$ .
Пустое слово принадлежит языку, поэтому ${ Displaystyle Lambda (е ') = { varepsilon }}$ .
Автомат местного языка
${ 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. Все переходы на букву $у$ обозначить букву $у$ .
Получите автомат для ${ Displaystyle L (е)}$ удалив индексы.

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

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

За $Λ$ , надо
${ Displaystyle Lambda ( emptyset) = emptyset}$ ,
${ Displaystyle Lambda ( varepsilon) = { varepsilon }}$ ,
${ Displaystyle Lambda (а) = emptyset}$ за каждую букву $а$ ,
${ Displaystyle Лямбда (е + е) = Лямбда (е) чашка Лямбда (е)}$ ,
${ Displaystyle Lambda (е cdot f) = Lambda (e) cdot Lambda (f)}$ , и
${ Displaystyle Lambda (е ^ {*}) = { varepsilon }}$ .
За $п$ , надо
${ Displaystyle Р ( emptyset) = P ( varepsilon) = emptyset}$ ,
${ Displaystyle Р (а) = {а }}$ за каждую букву $а$ ,
${ Displaystyle Р (е + е) = Р (е) чашка Р (е)}$ ,
${ Displaystyle P (е cdot f) = P (e) чашка Lambda (e) P (f)}$ , и
${ Displaystyle Р (е ^ {*}) = Р (е)}$ .
Те же формулы используются и для $D$ , за исключением товара, где
${ Displaystyle D (е cdot f) = D (f) чашка D (e) Lambda (f)}$ .
Для набора множителей длины 2 имеем
${ Displaystyle F ( emptyset) = F ( varepsilon) = F (а) = emptyset}$ за каждую букву $а$ ,
${ Displaystyle F (е + е) = F (е) чашка F (f)}$ ,
${ Displaystyle F (е cdot f) = F (е) чашка F (f) чашка D (e) P (f)}$ , и
${ Displaystyle F (е ^ {*}) = F (е) чашка D (e) P (e)}$ .

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

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

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

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

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

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

Аналитик

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

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

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

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

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

[1] В.М. Глушкова (1961). «Абстрактная теория автоматов». Российские математические обзоры (на русском). 16: 1–53. Дои:10.1070 / rm1961v016n05abeh004112.

[Pin.2016-2] а ^б Жан-Эрик Пин (ноябрь 2016 г.). Математические основы теории автоматов (PDF). Париж.

[3] Жак Сакарович (февраль 2003 г.). Éléments de théorie des automates. Париж: Vuibert. ISBN 978-2711748075.

[Sakarovitch.2009-4] а ^б Жак Сакарович (2009). Элементы теории автоматов. Кембридж: Издательство Кембриджского университета. ISBN 9780521844253.

[5] Брюггеманн-Кляйн, Анна (1993). «Регулярные выражения в конечных автоматах». Теоретическая информатика. 12 (2): 197–213. Дои:10.1016/0304-3975(93)90287-4.

[1]

[2]

[3]

[4]

[5]

Navigation