Согласно теореме Клини любому регулярному выражению можно поставить в соответствие конечный автомат, который является формальной моделью алгоритма распознавания лексем, обозначаемых данным регулярным выражением. В наиболее общих терминах конечный автомат -распознаватель определяется конечным множеством характерных для него состояний входного потока и переходов между ними. Изменение состояния происходит при получении символов входного потока из заданного алфавита в соответствии с функцией переходов , которая определяет возможные последующие состояния по входному символу и текущему состоянию. Среди возможных состояний выделяется исходное (начальное) и заключительные (допускающие) состояния в которых конечный автомат-распознаватель может находиться, соответственно, при начале и завершении обработки лексем входного потока. Если входная последовательность символов может порождать последовательность переходов, которая может переводить конечный автомат из начального состояния в одно из заключительных, то она считается допускающей и принадлежит распознаваемому им регулярному множеству.

(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

Таблица 1

Лексический анализ. Регулярные языки и конечные автоматы

по общему количеству символов алфавита символов и знаков операций и скобок в записи r .

Базис . Автоматы для выражений длины 1: и показаны на следующем рисунке.

Рис. 5.1.

Заметим, что у каждого из этих трех автоматов множество заключительных состояний состоит из одного состояния.

Индукционный шаг . Предположим теперь, что для каждого регулярного выражения длины = 1 слово w можно разбить на k подслов: w=w 1 w 2 ... w k и все . Для каждого i= 1,... ,k слово w i переводит q 0 1 в q f 1 . Тогда для слова w в диаграмме M имеется путь

Следовательно, . Обратно, если некоторое слово переводит q 0 в q f , то либо оно есть либо его несет путь , который, перейдя из q 0 в q 0 1 и затем пройдя несколько раз по пути из q 0 1 в q f 1 и вернувшись из q f 1 в q 0 1 по -переходу, в конце концов из q f 1 по -переходу завершается в q f . Поэтому такое слово .

Из теорем 4.2 и 5.1 непосредственно получаем

Следствие 5.1 . Для каждого регулярного выражения можно эффективно построить детерминированный конечный автомат , который распознает язык, представляемый этим выражением.

Это утверждение - один из примеров теорем синтеза : по описанию задания (языка как регулярного выражения ) эффективно строится программа (ДКА), его выполняющая. Справедливо и обратное утверждение - теорема анализа .

Теорема 5.2 . По каждому детерминированному (или недетерминированному) конечному автомату можно построить регулярное выражение , которое представляет язык, распознаваемый этим автоматом.

Доказательство этой теоремы достаточно техническое и выходит за рамки нашего курса.

Таким образом, можно сделать вывод , что класс конечно автоматных языков совпадает с классом регулярных языков . Далее мы будем называть его просто классом автоматных языков .

Автомат M r , который строится в доказательстве теоремы 5.1

Основные определения Регулярные выражения в алфавите Σ и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом: 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)(? !))$".

Описывать лексику языка удобнее в форме регулярных выражений, а распознавать язык с помощью КА. Поэтому важно уметь преобразовывать определения языка в форме регулярных выражений в определение в форме КА. Такое преобразование предложил 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.

	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 принадлежит регулярному множеству, распознаваемому рассмотренным ДКА и удовлетворяет приведенному выше регулярному выражению.

В заключение следует отметить, что рассмотренный неформальный способ конструирования

Для дальнейшего изучения свойств конечных автоматов и, в частности, для решения задачи синтеза важное значение имеет следующая теорема.

Теорема 7.7 (теорема о детерминизации). Для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат.

Для того чтобы доказать теорему, нужно, во-первых, описать алгоритм построения детерминированного конечного автомата по исходному; во-вторых, обосновать этот алгоритм, строго доказав, что он действительно дает конечный автомат, который является детерминированным и эквивалентным исходному. Здесь мы приведем только сам алгоритм построения детерминированного автомата.

Преобразование произвольного конечного автомата к эквивалентному детерминированному осуществляется в два этапа: сначала удаляются дуги с меткой \lambda , затем проводится собственно детерминизация.

1. Удаление λ-переходов (дуг с меткой \lambda ).

Чтобы перейти от исходного конечного автомата M=(V,Q,q_0,F,\delta) к эквивалентному конечному автомату M"=(V,Q",q_0,F",\delta") без λ-переходов, достаточно в исходном графе M проделать следующие преобразования.

а. Все состояния, кроме начального, в которые заходят только дуги с меткой \lambda , удаляются; тем самым определяется множество Q" конечного автомата M" . Понятно, что Q"\subseteq Q . При этом полагаем, что начальное состояние остается прежним.

б. Множество дуг конечного автомата M" и их меток (тем самым и функция переходов M" ) определяется так: для любых двух состояний p,r\in Q",~ p\to_{a}r имеет место тогда и только тогда, когда a\in V , а в графе M имеет место одно из двух: либо существует дуга из p в r , метка которой содержит символ a , либо существует такое состояние q , что p\Rightarrow_{\lambda}^{+}q и q\to_{a}r . При этом вершина q , вообще говоря, может и не принадлежать множеству Q" , т.е. она может и исчезнуть при переходе к автомату M" (рис. 7.11). Если же q\in Q" , то, естественно, в M" сохранится дуга (q,r) и символ a будет одним из символов, принадлежащих метке этой дуги (рис. 7.12).

Таким образом, в M" сохраняются все дуги M , метки которых отличны от \lambda и которые соединяют пару (вершин) состояний из множества Q" (не удаляемых согласно п. а). Кроме этого, для любой тройки состояний p,q,r (не обязательно различных!), такой, что p,r\in Q" и существует путь ненулевой длины из p в q , метка которого равна \lambda (т.е. путь по λ-переходам), а из q в r ведет дуга, метка которой содержит символ a входного алфавита, в M" строится дуга из p в r , метка которой содержит символ a (см. рис. 7.11).

в. Множество заключительных состояний F" конечного автомата M" содержит все состояния q\in Q" , т.е. состояния конечного автомата M , не удаляемые согласно п. а, для которых имеет место q\Rightarrow_{\lambda}^{\ast}q_f для некоторого q_f\in F (т.е. либо состояние q само является заключительным состоянием конечного автомата M , либо из него ведет путь ненулевой длины по дугам с меткой \lambda в одно из заключительных состояний конечного автомата M ) (рис. 7.13).

2. Собственно детерминизация.

Пусть M=(Q,V,q_0,F,\delta) - конечный автомат без λ-переходов. Построим эквивалентный M детерминированный конечный автомат M_1 .

Этот конечный автомат определяется таким образом, что его множество состояний есть множество всех подмножеств множества состояний конечного автомата M . Это значит, что каждое отдельное состояние конечного автомата M_1 определено как некоторое подмножество множества состояний конечного автомата M . При этом начальным состоянием нового конечного автомата (т.е. M_1 ) является одноэлементное подмножество, содержащее начальное состояние старого конечного автомата (т.е. M ), а заключительными состояниями нового конечного автомата являются все такие подмножества Q , которые содержат хотя бы одну заключительную вершину исходного конечного автомата M .

Впредь, допуская некоторую вольность речи, мы будем иногда называть состояния конечного автомата M_1 состояниями-множествами. Важно, однако, четко усвоить, что каждое такое состояние-множество есть отдельное состояние нового конечного автомата, но никак не множество его состояний. В то же время для исходного ("старого") конечного автомата M это именно множество его состояний. Образно говоря, каждое подмножество состояний старого конечного автомата "свертывается" в одно состояние нового конечного автомата*.

*Формально следовало бы определить множество Q_1 как множество, находящееся во взаимно однозначном соответствии с множеством 2^Q , но нам все-таки удобнее считать, что Q_1 совпадает с 2^Q , - ведь множеством состояний конечного автомата может быть любое непустое конечное множество.

Функция переходов нового конечного автомата определена так, что из состояния-множества S по входному символу а конечный автомат M_1 переходит в состояние-множество, представляющее собой объединение всех множеств состояний старого конечного автомата, в которые этот старый конечный автомат переходит по символу а из каждого состояния множества S . Таким образом, конечный автомат M_1 является детерминированным по построению.

Приведенное выше словесное описание можно перевести в формулы следующим образом: строим конечный автомат M_1 так, что

M_1=(Q_1,V,\{q_0\},F_1,\delta_1) , где

\begin{cases}Q_1=2^Q,\quad F_1=\{T\colon\, T\cap F\ne\varnothing,~T\in2^Q\},\\ (\forall S\subseteq Q)(\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_{q\in S}\delta(q,a)\Bigr). \end{cases}

Обратим внимание на то, что среди состояний нового конечного автомата есть состояние \varnothing , причем, согласно (7.8), \delta_1(\varnothing,a)=\varnothing для любого входного символа a . Это значит, что, попав в такое состояние, конечный автомат M_1 уже его не покинет. Вообще же любое состояние q конечного автомата, такое, что для любого входного символа a имеем \delta(q,a)=q , называют поглощающим состоянием конечного автомата. Таким образом, состояние \varnothing детерминированного конечного автомата M_1 является поглощающим. Полезно заметить также, что \delta_1(S,a)=\varnothing тогда и только тогда, когда для каждого q\in S (состояния старого конечного автомата из множества состояний S ) \delta(q,a)=\varnothing , т.е. в графе M из каждого такого состояния q не выходит ни одна дуга, помеченная символом a .

Можно доказать, что полученный по такому алгоритму конечный автомат эквивалентен исходному.

Пример 7.9. Детерминизируем конечный автомат, изображенный на рис. 7.14.

Эквивалентный конечный автомат без λ-переходов изображен на рис. 7.15. Заметим, что вершина q_2 исчезает, так как в нее заходят только "пустые" дуги.

Чтобы детерминизировать полученный автомат, совершенно не обязательно выписывать все его 2^3=8 состояний, среди которых многие могут оказаться не достижимыми из начального состояния \{q_0\} . Чтобы получить достижимые из \{q_0\} состояния, и только их, воспользуемся так называемым методом вытягивания.

Этот метод в общем случае можно описать так.

В исходном конечном автомате (без пустых дуг) определяем все множества состояний, достижимых из начального, т.е. для каждого входного символа a находим множество \delta(q_0,a) . Каждое такое множество в новом автомате является состоянием, непосредственно достижимым из начального.

Для каждого из определенных состояний-множеств S и каждого входного символа a находим множество \textstyle{\mathop{\bigcup\limits_{q\in S} \delta(q,a)}\limits^{\phantom{A}^{.}}} . Все полученные на этом шаге состояния будут состояниями нового (детерминированного) автомата, достижимыми из начальной вершины по пути длины 2. Описанную процедуру повторяем до тех пор, пока не перестанут появляться новые состояния-множества (включая пустое!). Можно показать, что при этом получаются все такие состояния конечного автомата M_1 , которые достижимы из начального состояния \{q_0\} .

Для конечного автомата на рис. 7.15 имеем:

\begin{aligned}& \delta_1(\{q_0\},a)=\{q_1\};\qquad \delta_1(\{q_0\},b)=\{q_1,q_3\};\\ & \delta_1(\{q_1\},a)=\{q_1\};\qquad \delta_1(\{q_1\},b)=\{q_1\};\\ & \delta_1(\{q_1,q_3\},a)= \delta(q_1,a)\cup \delta(q_3,a)= \{q_1\}\cup\{q_1\}=\{q_1\};\\ & \delta_1(\{q_1,q_3\},b)= \delta(q_1,b)\cup \delta(q_3,b)= \{q_1\}\cup\{q_1\}=\{q_1\}. \end{aligned}

Так как новых состояний-множеств больше не появилось, процедура "вытягивания" на этом заканчивается, и мы получаем граф, изображенный на рис. 7.16.

Дополнение регулярного языка

Одним из важных теоретических следствий теоремы о детерминизации является следующая теорема.

Теорема 7.8. Дополнение регулярного языка есть регулярный язык.

Пусть L - регулярный язык в алфавите V . Тогда дополнение языка L (как множества слов) есть язык \overline{L}=V^{\ast}\setminus L .

Согласно теореме 7.7, для регулярного языка L может быть построен детерминированный конечный автомат M , допускающий L . Поскольку в детерминированном автомате из каждой вершины по каждому входному символу определен переход в точности в одну вершину, то, какова бы ни была цепочка x в алфавите V , для нее найдется единственный путь в M , начинающийся в начальном состоянии, на котором читается цепочка x . Ясно, что цепочка x допускается автоматом M , то есть x\in L(M) , тогда и только тогда, когда последнее состояние указанного пути является заключительным. Отсюда следует, что цепочка x\notin L(M) тогда и только тогда, когда последнее состояние указанного пути не заключительное. Но нам как раз и нужен конечный автомат M" , который допускает цепочку x тогда и только тогда, когда ее не допускает исходный конечный автомат M . Следовательно, превращая каждое заключительное состояние M в не заключительное и наоборот, получим детерминированный автомат, допускающий дополнение языка L .

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

Пример 7.10. а. Построим конечный автомат, допускающий все цепочки в алфавите \{0;1\} , кроме цепочки 101.

Сначала построим конечный автомат, допускающий единственную цепочку 101. Этот автомат приведен на рис. 7.17.

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

И наконец, переходя к дополнению (и переименовывая состояния), получим автомат, изображенный на рис. 7.19.

Обратим внимание, что в полученном автомате все вершины, кроме вершины s_3 , являются заключительными.

Заметим также, что переход к дополнению, о котором идет речь в доказательстве теоремы 7.8, может быть проведен только в детерминированном автомате. Если бы мы поменяли ролями заключительные и незаключительные вершины в автомате, изображенном на рис. 7.17, то получили бы автомат, допускающий язык \{\lambda,1,10\} , который не является - как нетрудно сообразить - множеством всех цепочек, отличных от цепочки 101.

Отметим также, что конечный автомат на рис. 7.19 допускает все цепочки, содержащие вхождение цепочки 101, но не совпадающие с самой этой цепочкой. Вот, например, путь, несущий цепочку 1011: s_0,s_1,s_2,s_3,t .

б. Построим конечный автомат, допускающий все цепочки в алфавите \{0;1\} , кроме тех, которые содержат вхождение цепочки 101. Рассмотрим язык L , каждая цепочка которого содержит вхождение цепочки 101. Его можно задать так:

L=(0+1)^{\ast}101(0+1)^{\ast}.

Нам нужно построить автомат для дополнения языка L .

Непосредственно по регулярному выражению в этом случае легко построить конечный автомат, допускающий язык L (рис. 7.20).

Затем методом "вытягивания" проведем детерминизацию. Результат детерминизации представлен на рис. 7.21.

Для полного решения задачи осталось только на рис. 7.21 поменять ролями заключительные и не заключительные вершины (рис. 7.22).

в. Обсудим идею построения конечного автомата, допускающего те и только те цепочки в алфавите \{0;1\} , которые не начинаются цепочкой 01 и не заканчиваются цепочкой 11 (т.е. не разрешаются цепочки вида 01x и цепочки вида y11 , каковы бы ни были цепочки x,y\in\{0;1\} ).

В этом случае дополнением языка, для которого нужно построить конечный автомат, является множество всех таких цепочек нулей и единиц, которые начинаются цепочкой 01 или заканчиваются цепочкой 11. Допускающий это множество цепочек автомат строится как автомат для объединения 01(0+1)^{\ast}+(0+1)^{\ast}11 тем способом, который изложен при доказательстве теоремы Клини (см. теорему 7.6).

Из свойства замкнутости класса регулярных языков относительно дополнения (см. теорему 7.8) немедленно вытекает замкнутость этого класса относительно пересечения, теоретико-множественной и симметрической разности.

Следствие 7.3. Для любых двух регулярных языков L_1 и L_2 справедливы следующие утверждения:

1) пересечение L_1\cap L_2 регулярно;
2) разность L_1\setminus L_2 регулярна;
3) симметрическая разность L_1\vartriangle L_2 регулярна.

Справедливость утверждений вытекает из тождеств:

\begin{aligned} &{\scriptstyle{\mathsf{1)}}}\quad L_1\cap L_2= \overline{\overline{L_1} \cup\overline{L_2}}\,;\\ &{\scriptstyle{\mathsf{2)}}}\quad L_1\setminus L_2= L_1\cap \overline{L_2}\,;\\ &{\scriptstyle{\mathsf{3)}}}\quad L_1\,\triangle\,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end{aligned}

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

Согласно определению 7.10, конечные автоматы эквивалентны, если допускаемые ими языки совпадают. Поэтому, чтобы убедиться в эквивалентности автоматов M_1 и M_2 , достаточно доказать, что симметрическая разность языков L(M_1) и L(M_2) пуста. Для этого, в свою очередь, достаточно построить автомат, допускающий эту разность, и убедиться в том, что допускаемый им язык пуст. В общем случае проблему распознавания того, что язык конечного автомата пуст, называют проблемой пустоты для конечного автомата. Чтобы решить эту проблему, достаточно найти множество заключительных состояний автомата, достижимых из начального состояния. Так как конечный автомат - это ориентированный граф, то решить такую проблему можно, например, с помощью, поиска в ширину. Язык, допускаемый конечным автоматом, пуст тогда и только тогда, когда множество заключительных состояний, достижимых из начального состояния, пусто. Практически эквивалентность конечных автоматов предпочтительнее распознавать, используя алгоритм минимизации, но сейчас нам важно подчеркнуть, что принципиальная возможность решить проблему эквивалентности вытекает из теоремы 7.7 и ее алгебраических следствий.

КАТЕГОРИИ