Основные определения Регулярные выражения в алфавите Σ и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом: 1) – регулярное выражение, обозначающее регулярное множество; 2) e – регулярное выражение, обозначающее регулярное множество {e}; 3) если a Σ, то a – регулярное выражение, обозначающее регулярное множество {a}; 4) если p и q – регулярные выражения, обозначающие регулярные множества P и Q, то а) (p+q) – регулярное выражение, обозначающее P Q; б) pq – регулярное выражение, обозначающее PQ; в) p* – регулярное выражение, обозначающее P*; 5) ничто другое не является регулярным выражением.
Основные определения Расстановка приоритетов: * (итерация) – наивысший приоритет; конкатенация; + (объединение). Таким образом, 0 + 10* = (0 + (1 (0*))). Примеры: 1. 01 означает {01}; 2. 0* – {0*}; 3. (0+1)* – {0, 1}*; 4. (0+1)* 011 – означает множество всех цепочек, составленных из 0 и 1 и оканчивающихся цепочкой 011; 5. (a+b) (a+b+0+1)* означает множество всех цепочек {0, 1, a, b}*, начинающихся с a или b.
Основные определения Леммы: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α(β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Связь РВ и РМ РМ – языки, порождаемые РВ. Например: x = a+b, y = c+d, x X = {a, b}, y Y = {c, d}, x + y X Y = {a, b, c, d}. Конкатенация: xy XY = {ac, ad, bc, bd}. к(и+о)т {к}{и, о}{т} = {кит, кот} или по леммам № 5 и № 6 к(и+о)т = кит + кот {кит, кот}. Итерация: x = a, x* X* = {e, a, aaa, …}, т. е. x* = e + xxx + …
Связь РВ и РМ Итерация конкатенации и объединения: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx + … Пример: 0 + 1(0+1)* {0} ({1} {0, 1}*) = {0, 1, 10, 11, 100, 101, 110, 111…}. Объединение коммутативно: x + y = y + x Конкатенация – нет: xy ≠ yx
Связь РВ и РМ Примеры на приоритет: x + yz {x, yz}, (x + y)z {xz, yz}, x + y* {e, x, y, yyy, yyyy, …}, (x + y)* {e, x, y, xx, xy, yx, yy, xxx, …}, (xy)* {e, xyxy, …}, xy* {x, xyy, xyyy, …}. Новые леммы: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; и т. д.
Регулярные системы уравнений Уравнение с регулярными коэффициентами X = a. X + b имеет решение (наименьшую неподвижную точку) a*b: aa*b + b = (aa* + e)b = a*b Система уравнений с регулярными коэффициентами: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 = α 20 + α 21 X 1 + α 22 X 2 + … + α 2 n. Xn …………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Неизвестные – Δ = {X 1, X 2, …, Xn}.
Регулярные системы уравнений Алгоритм решения (метод Гаусса): Шаг 1. Положить i = 1. Шаг 2. Если i = n, перейти к шагу 4. Иначе записать уравнения для Xi в виде Xi = αXi + β (β = β 0 + βi+1 Xi+1 + … + βn. Xn). Затем в правых частях для уравнений Xi+1, …, Xn заменим Xi регулярным выражением α*β. Шаг 3. Увеличить i на 1 и вернуться к шагу 2. Шаг 4. Записать уравнение для Xn в виде Xn = αXn + β. Перейти к шагу 5 (при этом i = n). Шаг 5. Уравнение для Xi имеет вид Xi = αXi + β. Записать на выходе Xi = α*β, в уравнениях для Xi– 1, …, X 1 подставляя α*β вместо Xi. Шаг 6. Если i = 1, остановиться, в противном случае уменьшить i на 1 и вернуться к шагу 5.
Преобразование ДКА в РВ Для ДКА M = (Q, Σ, δ, q 0, F) составим систему с регулярными коэффициентами где Δ = Q: 1. полагаем αij: = ; 2. если δ(Xi, a) = Xj, a Σ, то αij: = αij + a; 3. если Xi F или δ(Xi,) = HALT, то αi 0: = e. После решения искомое РВ будет X 1 = q 0.
Преобразование ДКА в РВ Пример: для числа с фиксированной точкой получим систему q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 Здесь: s – знак числа, s = "+" + "–"; p – десятичная точка, p = ". "; d – цифры, d = "0" + "1" + … + "9".
Преобразование ДКА в РВ Решение: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. Из третьего уравнения: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). Из четвертого уравнения: q 4 = dq 4 + e = d*.
Преобразование ДКА в РВ Обратный ход: q 3 = d*(pq 4 + e) = d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd* + dd*(pd* + e), q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Таким образом, данному ДКА соответствует РВ s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Упростим: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Для более короткой записи можно использовать положительную итерацию aa* = a*a = a+: (s + e)(pdd* + dd*(pd* + e)) = (s + e)(pd+ + d+pd* + d+)
Преобразование ДКА в РВ Сопоставление графа функции переходов ДКА основным операциям с регулярными выражениями: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
Преобразование ДКА в РВ Более сложные комбинации операций: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*
Преобразование ДКА в РВ Для РВ (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d
Программирование РВ Регулярные выражения: Встроены во многие языки программирования (PHP, Java. Script, …); Реализованы в виде подключаемых компонентов (например, класс Regex для платформы. NET). Отличия в формах записи: x? = x + e x{1, 3} = x + xxx и т. д.
Программирование РВ Конструкции класса Regex (System. Text. Regular. Expressions): Символ Интерпретация Escape-последовательности b При использовании его в квадратных скобках соответствует символу «←» (u 0008) t, r, n, a, f, v Табуляция (u 0009), возврат каретки (u 000 D), новая строка (u 000 A) и т. д. c. X Управляющий символ (например, c. C – это Ctrl+C, u 0003) e Escape (u 001 B) ooo Символ ASCII в восьмеричной системе xhh Символ ASCII в шестнадцатеричной системе uhhhh Символ Unicode Следующий символ не является специальным символом РВ. Этим символом нужно экранировать все специальные символы Пример (в примере приведен шаблон и строка поиска, в строке найденные совпадения подчеркнуты): @"rnw+" – "rn. Здесь имеютсяnдве строки".
Программирование РВ Подмножества символов. Любой символ, кроме конца строки (n) Любой символ из множества [^xxx] Любой символ, кроме символов из множества Любой символ из диапазона ] Вычитание одного множества или диапазона из другого p{name} Любой символ, заданный категорией Unicode с именем name P{name} Любой символ, кроме заданных категорией Unicode с именем name w Множество символов, используемых при задании идентификаторов W Множество символов, не используемых при задании идентификаторов s Пробелы S Все, кроме пробелов d Цифры D Не цифры Примеры: @". +" – "rn. Здесь имеютсяnдве строки"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p{Lu}" – "City Lights"; // Lu – прописные буквы @"P{Lu}" – "City"; @"p{Is. Cyrillic}" – "ха. OS"; // Is. Cyrillic – русские буквы
Программирование РВ Привязка ^, A В начале строки $, Z В конце строки или до символа «n» в конце строки z В конце строки G В том месте, где заканчивается предыдущее соответствие b Граница слова B Любая позиция не на границе слова Примеры: @"G(d)" – "(1)(3)(5)(9) "; // три соответствия (1), (2) и (3) @"bnS*ionb" – "nation donation"; @"Bendw*b" – "end sends endure lender".
Программирование РВ Операции (кванторы) *, *? Итерация +, +? Положительная итерация? , ? ? Ноль или одно соответствие {n}, {n}? Точно n соответствий {n, }, {n, }? По меньшей мере, n соответствий {n, m}, {n, m}? От n до m соответствий Примеры (первые кванторы – жадные, ищут как можно большее число элементов, вторые – ленивые, ищут как можно меньшее число элементов): @"d{3, }" – "888 -5555"; @"^d{3}" – "913 -913"; @"-d{3}$" – "913 -913"; @"5+? 5" – "888 -5555"; // три совпадения – 55, 55 и 55 @"5+5" – "888 -5555".
Программирование РВ Группирование () Группа, автоматически получающая номер (? :) Не сохранять группу (?) или (? "имя") При обнаружении соответствия создается именованная группа (?) или Удаление ранее определенной группы и (? "имя– имя") сохранение в новой группе подстроки между ранее определенной группой и новой группой (? imnsx:) Включает или выключает в группе любую из пяти (? –imnsx:) возможных опций: i – нечувствительность к регистру; s – одна строка (тогда «. » – это любой символ); m – многострочный режим («^» , «$» – начало и конец каждой строки); n – не захватывать неименованные группы; x – исключить не преобразованные в escapeпоследовательность пробелы из шаблона и включить комментарии после знака номера (#) (? =) Положительное утверждение просмотра вперед нулевой длины
Программирование РВ (? !) Отрицательное утверждение просмотра вперед нулевой длины (?) Невозвращаемая (жадная) часть выражения Примеры: @"(an)+" – "bananas annals"; @"an+" – "bananas annals"; // сравните, три совпадения – an, an и ann @"(? i: an)+" – "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://сайт/presentation/-112203859_437213351/image-24.jpg" alt="Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";
Программирование РВ Подстановки $число Замещается часть строки, соответствующая группе с указанным номером ${имя} Замещается часть строки, соответствующая группе с указанным именем $$ Подставляется $ $& Замещение копией полного соответствия $` Замещение текста входной строки до соответствия $" Замещение текста входной строки после соответствия $+ Замещение последней захваченной группы $_ Замещение всей строки Комментарии (? #) Встроенный комментарий # Комментарий до конца строки
Программирование РВ Результаты работы Regex: Regex Matches() Match. Collection Match Groups() Group. Collection Group Captures() Capture. Collection Captures()
Программирование РВ Пример на языке C++ CLI (Visual C++/CLR/Консольное приложение CLR): int main() { Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r->Match(L"123 456"); int match. Count = 0; while (m->Success) { Console: : Write. Line(L"Соответствие {0}", ++match. Count); for (int i = 1; i Groups->Count; i++) { Group ^g = m->Groups[i]; Console: : Write. Line(L" Группа {0} = "{1}"", i, g->Value); for (int j = 0; j Captures->Count; j++) { Capture ^c = g->Captures[j]; Console: : Write. Line(L" Захват {0} = "{1}", позиция = {2}, длина = {3}", j, c, c->Index, c->Length); } } m = m->Next. Match(); } return 0; } System: : Text: : Regular. Expressions
Включение действий и поиск ошибок Ограничение количества значащих цифр в числе: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = d s + e = s? = (+|-)? pd* + e = (pd*)? = (. d*)? @"(+|-)? (. d+|d+(. d*)?)" или @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = new Regex(@"^(+|-)? (. (? "digit"d)+|(? "digit"d)+(. (? "digit"d)*)?)$"); Match m = r. Match("+1. 23456789"); if (m. Success) { Group g = m. Groups["digit"]; if (g. Captures. Count
Включение действий и поиск ошибок Определение позиции ошибки: Regex r = new Regex(@"(+|-)? (. (? "digit"d)+|(? "digit"d)+(. (? "digit"d)*)?)"); string str = "+1. 2345!678"; Match m = r. Match(str); if (m. Success) { Group g = m. Groups["digit"]; if (g. Captures. Count 0) Console. Write. Line("Ошибка в позиции 1: неожиданный символ "{0}"", str); else if (m. Length
Включение действий и поиск ошибок Определение позиции ошибки: 1. первая позиция входной цепочки (1), если первое соответствие не начинается с позиции Index = 0; 2. позиция, следующая за последним соответствием (match. Length + 1), если она не совпадает с последней позицией входной цепочки; 3. позиция первого разрыва между соответствиями (match[i]. Index + match[i]. Length + 1), если символ, следующий за предыдущим соответствием, не является первым символом следующего соответствия.
Index) break; index = m[i]. Index + m[i]. Length; } Console. Write. Line("Ошибка в позиции {0} "{1}"", index + 1, str); } «abc. xyz. pqr» – правильно; «+abc. xyz. pqr» – ошибка в позиции 1 («+»); «abc. xyz. pqr!» – ошибка в позиции 12 («!»); «abc. xyz!. pqr» – ошибка в позиции 8 («!»).
Включение действий и поиск ошибок Но! «abc. xyz. +pqr» – ошибка в позиции 8 («. »). Новый вариант шаблона: @"w+(. w+)*(. (? !$))? " Проверка: «abc. xyz. +pqr» – ошибка в позиции 9 («+»); «abc. xyz. pqr. » – ошибка в позиции 12 («. »).
Сбалансированные определения: «(? "x")» добавляет в коллекцию с именем «x» один элемент; «(? "-x")» убирает из коллекции «x» один элемент; «(? (x)(? !))» проверяет, что в коллекции «x» не осталось элементов. Язык L, описывающий вложенные операторы языка Pascal «begin end; »: @"^s*((? "begins+)+(? "-begin"ends*; s*)+)*(? (begin)(? !))$".
В этом разделе мы сформируем важные вопросы, связанные с регулярными языками. Сначала нужно разобраться, что значит задать вопрос о некотором языке. Типичный язык бесконечен, поэтому бессмысленно предъявлять кому-нибудь цепочки этого языка и задавать вопрос, требующий проверки бесконечного множества цепочек. Гораздо разумнее использовать одно из конечных представлений языка, а именно: ДКА, НКА, ε- НКА или регулярное выражение.
Очевидно, что представленные таким образом языки будут регулярными. В действительности не существует способа представления абсолютно произвольных языков. В следующих главах предлагаются конечные методы описания более широких классов, чем класс регулярных языков, и можно будет рассматривать вопросы о языках из них. Однако алгоритмы разрешения многих вопросов о языках существуют только для класса регулярных языков. Эти же вопросы становятся “неразрешимыми” (не существует алгоритмов ответов на эти вопросы), если они поставлены с помощью более “выразительных” обозначений (используемых для выражения более широкого множества языков), чем представления, разработанные для регулярных языков.
Начнем изучение алгоритмов для вопросов о регулярных языках, рассмотрев способы, которыми одно представление языка преобразуется в другое. В частности, рассмотрим временную сложность алгоритмов, выполняющих преобразования. Затем рассмотрим три основных вопроса о языках.
1. Является ли описываемый язык пустым множеством?
2. Принадлежит ли некоторая цепочка w представленному языку?
3. Действительно ли два разных описания представляют один и тот же язык? (Этот вопрос часто называют “эквивалентностью” языков.)
2.1 Преобразования различных представлений языков
Каждое из четырех представлений регулярных языков можно преобразовать в любое из остальных трех. На рис. 3.1 представлены переходы от одного представления к другому. Хотя существуют алгоритмы для любого из этих преобразований, иногда нас интересует не только осуществимость некоторого преобразования, но и время, необходимое для его выполнения. В частности, важно отличать алгоритмы, которые занимают экспоненциальное время (время как функция от размера входных данных) и, следовательно, могут быть выполнены только для входных данных сравнительно небольших размеров, от тех алгоритмов, время выполнения которых является линейной, квадратичной или полиномиальной с малой степенью функцией от размера входных данных. Последние алгоритмы “реалистичны”, так как их можно выполнить для гораздо более широкого класса экземпляров задачи. Рассмотрим временную сложность каждого из обсуждавшихся преобразований.
Преобразование НКА в ДКА
Время выполнения преобразования НКА или ε-НКА в ДКА может быть экспоненциальной функцией от количества состояний НКА. Начнем с того, что вычисление ε-замыкания n состояний занимает время O(n3). Необходимо найти все дуги с меткой ε, ведущие от каждого из n состояний. Если есть n состояний, то может быть не более n2 дуг. Разумное использование системных ресурсов и хорошо спроектированные структуры данных гарантируют, что время исследования каждого состояния не превысит O(n2). В действительности для однократного вычисления всего ε-замыкания можно использовать такой алгоритм транзитивного замыкания, как алгоритм Уоршалла (Warshall)5.
После вычисления ε-замыкания можно перейти к синтезу ДКА с помощью конструкции подмножеств. Основное влияние на расход времени оказывает количество состояний ДКА, которое может равняться 2n. Для каждого состояния можно вычислить переходы за время O(n3), используя ε-замыкание и таблицу переходов НКА для каждого входного символа. Предположим, нужно вычислить δ({q1, q2, …, qk}, a) для ДКА. Из каждого состояния qi можно достичь не более n состояний вдоль путей с меткой ε, и каждое из этих состояний может иметь не более, чем n дуг с меткой a. Создав массив, проиндексированный состояниями, можно вычислить объединение не более n множеств, состоящих из не более, чем n состояний, за время, пропорциональное n2.
Таким способом для каждого состояния qi можно вычислить множество состояний, достижимых из qi вдоль пути с меткой a (возможно, включая дуги, отмеченные ε). Поскольку k ≤ n, то существует не более n таких состояний qi, и для каждого из них вычис-ление достижимых состояний занимает время O(n2). Таким образом, общее время вычисления достижимых состояний равно O(n3). Для объединения множеств достижимых состояний потребуется только O(n2) дополнительного времени, следовательно, вычисление одного перехода ДКА занимает время O(n3).
Заметим, что количество входных символов считается постоянным и не зависит от n. Таким образом, как в этой, так и в других оценках времени работы количество входных символов не рассматривается. Размер входного алфавита влияет только на постоянный коэффициент, скрытый в обозначении “О большого”.
Итак, время преобразования НКА в ДКА, включая ситуацию, когда НКА содержит ε-переходы, равно O(n32n). Конечно, на практике обычно число состояний, которые строятся, намного меньше 2n. Иногда их всего лишь n. Поэтому можно установить оценку времени работы равной O(n3s), где s - это число состояний, которые в действительности есть у ДКА.
Преобразование ДКА в НКА
Это простое преобразование, занимающее время O(n) для ДКА с n состояниями. Все, что необходимо сделать, - изменить таблицу переходов для ДКА, заключив в скобки {} состояния, а также добавить столбец для ε, если нужно получить ε-НКА. Поскольку число входных символов (т.е. ширина таблицы переходов) считается постоянным, копирование и обработка таблицы занимает время O(n).
Преобразование автомата в регулярное выражение
Каждом из n этапов (где n - число состояний ДКА) размер конструируемого регулярного выражения может увеличиться в четыре раза, так как каждое выражение строится из четырех выражений предыдущего цикла. Таким образом, простая запись n3 выражений может занять время O(n34n). Улучшенная конструкция из раздела 3.2.2 уменьшает постоянный коэффициент, но не влияет на экспоненциальность этой задачи (в наихудшем случае).
Аналогичная конструкция требует такого же времени работы, если преобразуется НКА, или даже ε-НКА, но это здесь не доказывается. Однако использование конструкции для НКА имеет большое значение. Если сначала преобразовать НКА в ДКА, а затем ДКА - в регулярное выражение, то на это потребуется время O(n34n32n), которое является дважды экспоненциальным.
Преобразование регулярного выражения в автомат
Для преобразования регулярного выражения в ε-НКА потребуется линейное время. Необходимо эффективно проанализировать регулярное выражение, используя метод, занимающий время O(n) для регулярного выражения длины n6. В результате получим дерево с одним узлом для каждого символа регулярного выражения (хотя скобки в этом дереве не встречаются, поскольку они только управляют разбором выражения).
Полученное дерево заданного регулярного выражения можно обработать, конструируя ε-НКА для каждого узла. Правила преобразования регулярного выражения, представленные в разделе 3.2.3, никогда не добавляют более двух состояний и четырех дуг для каждого узла дерева выражения. Следовательно, как число состояний, так и число дуг результирующего ε-НКА равны O(n). Кроме того, работа по созданию этих элементов в каждом узле дерева анализа является постоянной при условии, что функция, обрабатывающая каждое поддерево, возвращает указатели в начальное и допускающие состояния этого автомата.
Приходим к выводу, что построение ε-НКА по регулярному выражению занимает время, линейно зависящее от размера выражения. Можно исключить ε-переходы из ε- НКА с n состояниями, преобразовав его в обычный НКА за время O(n3) и не увеличив числа состояний. Однако преобразование в ДКА может занять экспоненциальное время.
Описывать лексику языка удобнее в форме регулярных выражений, а распознавать язык с помощью КА. Поэтому важно уметь преобразовывать определения языка в форме регулярных выражений в определение в форме КА. Такое преобразование предложил Kennet Thompson.
Конечный автомат это пятерка (S, S, d, S 0 , F)
S - конечное множество состояний.
S - конечное множество допустимых входных сигналов.
d - функция переходов. Она отражает множество Sх(SÈ{e}) в множество состояний недетерминированного конечного автомата. Для детерминированного автомата функция переходов отражает множество SхS во множество состояний автомата. Другими словами, в зависимости от состояния и входного символа, d определяет новое состояние автомата.
S 0 - начальное состояние конечного автомата, S 0 Î S.
F - множество конечных состояний автомата, F Î S.
Работа конечного автомата представляет собой последовательность шагов. Шаг определяется состоянием автомата и входным символом. Сам шаг состоит в изменении состояния автомата и считывании следующего символа входной последовательности.
Существуют следующие правила преобразования регулярных выражений в конечный автомат.
1 Регулярное выражение “e” преобразуется в автомат из двух состояний и e -перехода между ними (рисунок 1).
Рисунок 1. – Автомат для e-перехода
2 Регулярное выражение из одного символа “а” преобразуется в конечный автомат из двух состояний и перехода между ними по входному сигналу а (рисунок 2).
Рисунок 2. – Автомат для перехода по символу а
3 Пусть есть регулярное выражение rs и уже построены конечные автоматы для выражения r и выражения s. Тогда два автомата соединяются последовательно. На рисунке 3 представлены исходные автоматы для языков r и s. На рисунке автомат для распознавания конкатенации этих языков.
Автомат для r Автомат для s
Рисунок 3. – Исходные автоматы
Рисунок 4. – Автомат для конкатенации языков
4 Пусть есть регулярное выражение r | s и уже построены конечные автоматы для выражения r и выражения s (рисунок 3). Тогда в результирующем автомате должна быть альтернатива выполнения одного из двух автоматов. То есть автомат для выражения r | s при автоматах для r и s с рисунка 3 имеет вид, представленный на рисунке 5.
Рисунок 5. – Автомат для объединения языков
5 Пусть есть регулярное выражение r* при построенном конечном автомате r. В этом случае вводятся два новых состояния для возможности обхода автомата выражения r, а также вводится e-переход между конечным и начальным состояниями для возможности многократного повторения автомата r. Если для регулярного выражения r построен автомат аналогичный рисунку 3, то регулярному выражению r* соответствует конечный автомат, представленный на рисунке 6.
Настройки
Согласно теореме Клини любому регулярному выражению можно поставить в соответствие конечный автомат, который является формальной моделью алгоритма распознавания лексем, обозначаемых данным регулярным выражением. В наиболее общих терминах конечный автомат -распознаватель определяется конечным множеством характерных для него состояний входного потока и переходов между ними. Изменение состояния происходит при получении символов входного потока из заданного алфавита в соответствии с функцией переходов , которая определяет возможные последующие состояния по входному символу и текущему состоянию. Среди возможных состояний выделяется исходное (начальное) и заключительные (допускающие) состояния в которых конечный автомат-распознаватель может находиться, соответственно, при начале и завершении обработки лексем входного потока. Если входная последовательность символов может порождать последовательность переходов, которая может переводить конечный автомат из начального состояния в одно из заключительных, то она считается допускающей и принадлежит распознаваемому им регулярному множеству.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
Таблица 1
| 0 | 1 | |
| Q1 | Q4 | Q2 |
| Q2 | Q3 | Q1 |
| Q3 | Q2 | Q4 |
| Q4 | Q1 | Q3 |
Столбцы таблицы переходов обозначают символы входного алфавита, а строки соответствуют текущим состояниям ДКА . Элементы каждой строки указывают состояния ДКА , в которые он должен переходить из текущего состояния при получении соответствующих символов входного алфавита. В частности, из первой строки данной таблицы переходов следует, что получение символов 0 и 1 в начальном состоянии Q1 переводит ДКА в состояния Q4 и Q2, соответственно.
При распознавании входной последовательности по таблице переходов легко проследить изменения состояния ДКА с целью определить достигается или нет одно из допускающих состояний. В частности, для бинарного вектора 01001000 с четным числом нулей и единиц рассмотренный ДКА порождает следующую последовательность переходов, где каждый переход помечен вызывающим его символом входного алфавита:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Эта последовательность переходов завершается допускающим состоянием Q1, следовательно, бинарный вектор 01001000 принадлежит регулярному множеству, распознаваемому рассмотренным ДКА и удовлетворяет приведенному выше регулярному выражению.
В заключение следует отметить, что рассмотренный неформальный способ конструирования
Рассмотрим алгоритм построения по регулярному выражению недетерминированного конечного автомата, допускающего тот же язык.
Алгоритм 3.1 . Построение недетерминированного конечного автомата по регулярному выражению.
Вход . Регулярное выражение r в алфавите T .
Выход . НКА M , такой что L(M) = L(r) .
Метод .Автомат для выражения строится композицией из автоматов, соответствующих подвыражениям. На каждом шаге построения строящийся автомат имеет в точности одно заключительное состояние, в начальное состояние нет переходов из других состояний и нет переходов из заключительного состояния в другие.
Построение детерминированного конечного автомата по недетерминированномуРассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык.
Алгоритм 3.2 . Построение детерминированного конечного автомата по недетерминированному.
Вход . НКА M = (Q, T, D, q 0 , F) .
Выход . ДКА .
Метод . Каждое состояние результирующего ДКА - это некоторое множество состояний исходного НКА.
В алгоритме будут использоваться следующие функции: - множество состояний НКА, достижимых из состояний, входящих в R , посредством только переходов по e , то есть множество
Множество состояний НКА, в которые есть переход на входе a для состояний из R , то есть множество
Вначале Q" и D" пусты. Выполнить шаги 1-4:
(1) Определить .
(2) Добавить в Q" как непомеченное состояние
(3) Выполнить следующую процедуру:
(4) Определить .
Пример 3.6 . Результат применения алгоритма 3.2 приведен на рис. 3.10 .
Рис. 3.10. Построение детерминированного конечного автомата по регулярному выражению
Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [?] .
Пусть дано регулярное выражение r в алфавите T . К регулярному выражению r добавим маркер конца: (r)# . Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.
Алгоритм будет оперировать с синтаксическим деревом
для пополненного регулярного выражения (r)#,
каждый
лист которого помечен символом 
, а каждая
внутренняя вершина
помечена знаком одной из операций: (конкатенация), |
(объединение), *
(итерация).
Каждому листу дерева (кроме e -листьев) присвоим уникальный номер, называемый позицией, и будем использовать его, с одной стороны, для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ, соответствующий этому листу. Заметим, что если некоторый символ используется в регулярном выражении несколько раз, он имеет несколько позиций.
Обойдем дерево T снизу-вверх слева-направо и вычислим четыре функции: nullable,firstpos, lastpos и followpos . Три первые функции - nullable, firstpos и lastpos - определены на узлах дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable , является множество позиций. Функция followpos вычисляется через три остальные функции.
Функция firstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках , генерируемых подвыражением с вершиной в n . Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в
