Лексичний аналіз. Регулярні мови та кінцеві автомати
за загальною кількістю символів алфавіту символів та знаків операцій та дужок у записі 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. Після рішення шукане РВ буде X1 = q0.
Перетворення ДКА на РВ Приклад: для числа з фіксованою точкою отримаємо систему 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. З третього рівняння: q3 = dq3 + pq4 + e = d * (pq4 + 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 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) і т.д. X Керуючий символ (наприклад, c. C – це Ctrl+C, u 0003) e Escape (u 001 B) ooo Символ ASCII у восьмеричній системі xhh Символ ASCII у шістнадцятковій системі uhhhh Символ Unicode Наступний символ не є спеціальним символом РВ. Цим символом потрібно екранувати всі спеціальні символи Приклад (у прикладі наведено шаблон і рядок пошуку, у рядку знайдені збіги підкреслені): @"rnw+" - "rn. Тут є два рядки".
Програмування РВ Підмножини символів. Будь-який символ, крім кінця рядка (n) Будь-який символ з множини [^xxx] Будь-який символ, крім символів з множини Будь-який символ з діапазону ] Віднімання однієї множини або діапазону з іншої p(name) Будь-який символ, заданий категорією Unicode з ім'ям name P (name) Будь-який символ, крім заданих категорією Unicode з ім'ям name w Безліч символів, що використовуються при заданні ідентифікаторів W Безліч символів, що не використовуються при заданні ідентифікаторів s Пробіли S Усі, крім пробілів d Цифри D Не цифри Приклади: @". +" – "rn. Тут є два рядки"; @ "+" - "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; = 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(); Text: : Regular. Expressions
Увімкнення дій та пошук помилок Обмеження кількості значущих цифр у числі: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = ds + 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, S0, 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 належить регулярній множині, що розпізнається розглянутим ДКАта задовольняє наведеному вище регулярному виразу.
На закінчення слід зазначити, що розглянутий неформальний спосіб конструювання
Для подальшого вивчення властивостей кінцевих автоматів і, зокрема, на вирішення завдання синтезу важливе значення має така теорема.
Теорема 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 \) стану, і тільки їх, скористаємося так званим методом витягування.
Цей метод у випадку можна описати так.
У вихідному кінцевому автоматі (без порожніх дуг) визначаємо всі множини станів, досяжних з початкового, тобто. для кожного вхідного символу знаходимо безліч \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 . .
Доведена теорема дозволяє будувати кінцевий автомат, що не допускає певну множину ланцюжків, наступним методом: будуємо спочатку автомат, що допускає дану множину ланцюжків, потім детермінізуємо його і переходимо до автомата для доповнення так, як це зазначено у доказі теореми 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. 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 та її наслідків алгебри.
