Лексикален анализ. Редовни езици и крайни автомати
от общия брой знаци от азбуката на символите и знаците за операции и скоби в записа 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. За всеки регулярен израз може ефективно да се изгради детерминистична крайна машина, която разпознава езика, представен от този израз.
Това твърдение е един от примерите за теореми за синтез: въз основа на описанието на задача (език като регулярен израз), ефективно се конструира програма (DFA), която я изпълнява. Обратното също е вярно - теорема на анализа.
Теорема 5.2. За всяка детерминирана (или недетерминирана) крайна машина е възможно да се конструира регулярен израз, който представлява езика, разпознат от тази машина.
Доказателството на тази теорема е доста техническо и извън обхвата на нашия курс.
По този начин можем да заключим, че класът на крайно автоматичните езици съвпада с класа на редовните езици. Отсега нататък ще го наричаме просто класа на автоматните езици.
Автоматът M r, който е конструиран в доказателството на теорема 5.1
Основни дефиниции Регулярните изрази в азбуката Σ и регулярните множества, които те обозначават, се дефинират рекурсивно, както следва: 1) – регулярен израз, обозначаващ регулярен набор; 2) e – регулярен израз, обозначаващ регулярен набор (e); 3) ако a Σ, тогава a е регулярен израз, обозначаващ редовно множество (a); 4) ако p и q са регулярни изрази, обозначаващи регулярни множества P и Q, тогава a) (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) α+ = α
Връзка между RT и RM RM са езици, генерирани от RT. Например: 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). k(u+o)t (k)(u, o)(t) = (кит, котка) или по леми № 5 и № 6 k(u+o)t = кит + котка (кит, котка) . Итерация: x = a, x* X* = (e, a, aaa, …), т.е. x* = e + xxx + …
Връзка между RP и RM Итерация на конкатенация и обединение: (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
Комуникация между RM и RM Примери за приоритет: 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.
Трансформация на DFA в RT За DFA M = (Q, Σ, δ, q 0, F) съставяме система с регулярни коефициенти, където Δ = Q: 1. задайте αij: = ; 2. ако δ(Xi, a) = Xj, a Σ, тогава αij: = αij + a; 3. ако Xi F или δ(Xi,) = HALT, тогава αi 0: = e. След решаването желаната PV ще бъде X 1 = q 0.
Преобразуване на DFA в RV Пример: за число с фиксирана запетая получаваме системата 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”.
Преобразуване на DFA в RT Решение: 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*.
Преобразуване на DFA в RT Обратен ход: 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). По този начин този DFA съответства на RT 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+)
Преобразуване на DFA в RT Картографиране на графиката на функцията за преход на DFA към основни операции с регулярни изрази: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
Преобразуване на DFA в RT По-сложни комбинации от операции: 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*
Преобразуване на DFA в RT За RT (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
RV програмиране Регулярни изрази: Вградени в много езици за програмиране (PHP, Java. Script, ...); Внедрени като компоненти на добавки (например клас Regex за платформата .NET). Разлики във формите на нотация: x? = x + e x(1, 3) = x + xxx и т.н.
Програмиране на RT конструкции на класа Regex (Система. Текст. Редовни. Изрази): Интерпретация на символи на Escape последователността b Когато се използва в квадратни скоби, съответства на символа „←“ (u 0008) t, r, n, a, f, v Tab (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 знак Следният знак не е специален RT знак. Този символ трябва да се използва за екраниране на всички специални знаци Пример (примерът показва модел и низ за търсене, намерените съвпадения са подчертани в низа): @"rnw+" – "rn. Тук има два реда."
Програмиране на RV подмножества от символи. Всеки знак с изключение на края на реда (n) Всеки знак от набора [^xxx] Всеки знак с изключение на знаци от набора Всеки знак от диапазона ] Изваждане на един набор или диапазон от друг p(име) Всеки знак, определен от Unicode име на категория P (име) Всеки знак, различен от посочените от името на Unicode категорията w Набор от знаци, използвани при указване на идентификатори W Набор от знаци, които не се използват при уточняване на идентификатори s Интервали S Всички с изключение на интервали d Числа D Нецифри Примери : @". +" – "rn. Има ntдва реда"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p(Lu)" – „Светлините на града“; // Lu – главни букви @"P(Lu)" – "Град"; @"p(Is. Cyrillic)" – "ha. OS"; //Е. Кирилица - руски букви
Програмиране PB Anchor ^, A В началото на реда $, Z В края на реда или преди знака "n" в края на реда z В края на реда G Където завършва предишното съвпадение b Граница на думата B Всяка позиция извън границата на дума Примери: @ "G(d)" – "(1)(3)(5)(9)"; // три мача (1), (2) и (3) @"bnS*ionb" – "дарение на нация"; @"Bendw*b" – "край изпраща издържа заемодател".
Програмиране на RT операции (квантори) *, *? Итерация +, +? Положителна итерация? , ? ? Нула или едно съвпадение (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".
RV програмиране Групиране () Група, която автоматично получава номер (? :) Не запазвайте групата (?) или (? "име") Ако бъде намерено съвпадение, се създава наименувана група (?) или Изтрийте предварително дефинирана група и (? "име - име") запазване в нова група на подниз между предварително дефинирана група и нова група (? imnsx:) Активира или деактивира всяка от пет (? –imnsx:) възможни опции в група: i – нечувствителен към регистър; s – един ред (тогава “.” е произволен знак); m – многоредов режим (“^”, “$” – началото и края на всеки ред); n – не улавя неименувани групи; x – изключете неекранирани интервали от шаблона и включете коментари след знака за число (#) (? =) Изявление за положителен преглед с нулева дължина
RT програмиране (? !) Отрицателен изглед с нулева дължина (?) Невъзвръщаема (алчна) част от израз Примери: @"(an)+" – "bananas annals"; @"an+" – "летописи на банани"; // сравнение, три съвпадения - an, an и ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://site/presentation/-112203859_437213351/image-24.jpg" alt="RV Връзки за програмиране номер Връзка към група k Връзка към назована група Примери: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
Програмиране на RV замествания $номер Заменя частта от низа, съответстваща на групата с посочения номер $(име) Заменя частта от низа, съответстваща на групата с указаното име $$ Заменя $$& Заменя с копие на пълното match $` Заменя текста на въведения низ, докато съвпадне с $" Заменя текста на входните редове след съвпадение $+ Заменя последната заснета група $_ Заменя целия ред Коментари (? #) Вграден коментар # Коментар до края на реда
Програмиране на RT резултати от Regex: Regex Matches() Match. Колекция Match Groups() Група. Колекция Group Captures() Capture. Колекция Capture()
Пример за програмиране на RV в 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"Match (0)", ++match. Count); for (int i = 1; i Groups->Count; i++) ( Group ^g = m->Groups[i]; Console: : Write. Line(L" Group (0) = "(1)"", i, g-> Value ); for (int j = 0; j Captures->Count; j++) ( Capture ^c = g->Captures[j]; Console: : Write. Line(L" Capture (0) = "(1)" , позиция = (2), дължина = (3)", j, c, c->Индекс, c->Дължина); ) ) m = m->Следващ. Съвпадение(); ) връща 0; ) Система: : Текст : : Редовен. Изрази
Разрешаване на действия и намиране на грешки Ограничаване на броя на значещите цифри в число: (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 = нов Regex (@"^(+|-)? (. (? "цифра"d)+|(? "цифра"d)+(. (? "цифра"d)*)?)$"); Съвпадение m = r. Съвпадение ("+1. 23456789"); if (m. Успех) ( Group g = m. Groups["digit"]; if (g. Captures. Count)
Активиране на действия и намиране на грешки Определяне на позицията на грешката: Regex r = new Regex(@"(+|-)? (. (? "цифра"d)+|(? "цифра"d)+(. (? "цифра" д )*)?)"); низ str = "+1. 2345!678"; Съвпадение m = r. Съвпадение (str); if (m. Успех) ( Group g = m. Groups["digit"]; if (g. Captures. Count 0) Console. Write. Line("Greška at position 1: unexpected character "(0)"", str ); иначе ако (м. Дължина
Разрешаване на действия и търсене на грешки Определяне на позицията на грешката: 1. първата позиция на входната верига (1), ако първото съвпадение не започва от позиция Index = 0; 2. позицията след последното съвпадение (съвпадение. дължина + 1), ако не съвпада с последната позиция на входната верига; 3. позиция на първата празнина между съвпаденията (match[i]. Index + match[i]. Length + 1), ако знакът след предишното съвпадение не е първият символ на следващото съвпадение.
Индекс) прекъсване; индекс = m[i]. Индекс + m[i]. Дължина; ) Конзола. Пишете. Line("Грешка в позиция (0) "(1)"", индекс + 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*((? "започва+)+(? "-започва"завършва*; s*)+)*(? (започва)(? !))$".
По-удобно е да се опише речникът на даден език под формата на регулярни изрази и да се разпознае езикът с помощта на CA. Следователно е важно да можете да конвертирате езикови дефиниции под формата на регулярни изрази в дефиниция под формата на CA. Тази трансформация е предложена от Кенет Томпсън.
Крайният автомат е пет (S, S, d, S 0 , F)
S е краен набор от състояния.
S е краен набор от валидни входни сигнали.
d - преходна функция. Той отразява множеството Sx(SÈ(e)) в множеството от състояния на недетерминиран краен автомат. За детерминиран автомат преходната функция отразява набора SxS в набора от състояния на автомата. С други думи, в зависимост от състоянието и входния символ d определя новото състояние на машината.
S 0 - начално състояние на крайния автомат, S 0 О S.
F е множеството от крайни състояния на автомата, F О S.
Работата на краен автомат е последователност от стъпки. Стъпката се определя от състоянието на машината и символа за въвеждане. Самата стъпка се състои в промяна на състоянието на машината и четене на следващия символ от входната последователност.
Съществуват следните правила за преобразуване на регулярни изрази в крайна машина.
1 Регулярният израз “e” се трансформира в автомат от две състояния и е-преход между тях (Фигура 1).
Фигура 1. – Автоматична машина за е-преход
2 Регулярен израз от един знак „a“ се преобразува в краен автомат от две състояния и преход между тях въз основа на входния сигнал a (Фигура 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, а също така се въвежда е-преход между крайното и началното състояние, за да се направи възможно повторението на автомата 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 |
Колоните на таблицата за преход показват знаците на въведената азбука, а редовете съответстват на текущите състояния на DFA. Елементите на всеки ред показват състоянията на DFA, към което трябва да премине от текущото състояние при получаване на съответните знаци от въведената азбука. По-специално, от първия ред на тази таблица на прехода следва, че получаването на символите 0 и 1 в първоначалното състояние Q1 преобразува DFAдо състояния Q4 и Q2, съответно.
При разпознаване на входна последователност с помощта на таблицата за преход е лесно да се проследят промените в състоянието на DFAза да се определи дали едно от разрешаващите състояния е постигнато или не. По-специално, за двоичния вектор 01001000 с четен брой нули и единици, разглежданият DFAгенерира следната последователност от преходи, където всеки преход е обозначен със символа на въведената азбука, която го причинява:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Тази последователност от преходи завършва с допускащо състояние Q1, следователно двоичният вектор 01001000 принадлежи към редовния набор, разпознат от разглеждания DFAи удовлетворява горния регулярен израз.
В заключение трябва да се отбележи, че разглежданият неформален метод на конструиране
За по-нататъшно изследване на свойствата на крайните автомати и по-специално за решаване на проблема със синтеза е важна следната теорема.
Теорема 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. В същото време приемаме, че първоначалното състояние остава същото.
b. Множеството от дъги на крайния автомат 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" , тогава, естествено, дъгата (q,r) ще се запази в M" и символът a ще бъде един от символите принадлежащи към етикета на тази дъга (фиг. 7.12).
По този начин в M" се съхраняват всички дъги M, чиито етикети са различни от \lambda и които свързват двойка (върхове) състояния от множеството Q" (не се изтриват съгласно част a). В допълнение, за всяка тройка от състояния p,q,r (не непременно различни!), такава, че p,r\in Q" и има път с ненулева дължина от p до q, етикетът на който е равен до \lambda (т.е. пътят чрез λ-преходи), и дъга води от q до r, чийто етикет съдържа символа a на входната азбука; в M" се изгражда дъга от p към r, етикетът на който съдържа символа a (виж фиг. 7.11).
V. Наборът от крайни състояния F" на крайния автомат M" съдържа всички състояния q\in Q", т.е. състояния на крайния автомат M, които не са изтрити съгласно параграф a, за които 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_1, еквивалентен на M.
Този краен автомат е дефиниран по такъв начин, че неговото множество от състояния е множеството от всички подмножества на множеството от състояния на крайния автомат M. Това означава, че всяко отделно състояние на крайния автомат M_1 се определя като определено подмножество от множеството състояния на крайния автомат M. В този случай първоначалното състояние на новия краен автомат (т.е. M_1) е единично подмножество, съдържащо началното състояние на стария краен автомат (т.е. M), а крайните състояния на новия краен автомат са всички такива подмножества Q, които съдържат поне един краен връх на оригиналния краен автомат M.
Оттук нататък, позволявайки известна свобода на словото, понякога ще наричаме състоянията на крайния автомат M_1 набори от състояния. Важно е обаче ясно да се разбере, че всеки такъв набор от състояния е отделно състояние на нов краен автомат, но не набор от неговите състояния. В същото време за оригиналния („стар“) краен автомат M това е именно множеството от неговите състояния. Образно казано, всяко подмножество от състояния на стария краен автомат се „свива“ в едно състояние на новия краен автомат*.
*Формално трябва да дефинираме множеството Q_1 като множество, което е във взаимно съответствие с множеството 2^Q, но все пак за нас е по-удобно да приемем, че Q_1 съвпада с 2^Q - в крайна сметка, набор от състояния на краен автомат може да бъде всяко непразно крайно множество.
Преходната функция на новия краен автомат е дефинирана така, че от набора от състояния S чрез входния символ a крайният автомат M_1 преминава към набора от състояния, който е обединението на всички набори от състояния на стария краен автомат, в които този стар краен автомат върви със символа a от всяко множество от състояния 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). \край (случаи)
Нека обърнем внимание на факта, че сред състоянията на новия краен автомат има състояние \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)\чаша \delta(q_3,b)= \(q_1\)\чаша\(q_1\)=\(q_1\). \край (подравнено)
Тъй като не са се появили нови набори от състояния, процедурата за „дърпане“ приключва тук и получаваме графиката, показана на фиг. 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.
b. Нека изградим краен автомат, който приема всички вериги в азбуката \(0;1\), с изключение на тези, които съдържат срещане на верига 101. Да разгледаме език L, всяка верига от който съдържа срещане на верига 101. Може да бъде определени, както следва:
L=(0+1)^(\ast)101(0+1)^(\ast).
Трябва да изградим автомат, който да допълва езика L.
В този случай, използвайки директно регулярния израз, е лесно да се конструира краен автомат, който приема езика L (фиг. 7.20).
След това ще извършим детерминизация с помощта на метода „издърпване“. Резултатът от определянето е представен на фиг. 7.21.
За пълно решаване на проблема остава всичко, което е на фиг. 7.21 разменете ролите на крайните и некрайните върхове (фиг. 7.22).
V. Нека обсъдим идеята за конструиране на краен автомат, който позволява онези и само онези вериги в азбуката \(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\varтриъгълник 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\чаша L_2)\setminus (L_1\cap L_2).\край (подравнено)
Първо, получените резултати ни позволяват да твърдим, че класът на регулярните езици по отношение на операциите на обединение, пресичане и добавяне е булева алгебра, в която единицата е универсалният език, а нулата е празният език. Второ, тези алгебрични свойства на семейството от редовни езици ни позволяват да разрешим важния проблем с разпознаването на еквивалентността на два произволни крайни автомата.
Съгласно дефиниция 7.10 крайните автомати са еквивалентни, ако езиците, които приемат, са еднакви. Следователно, за да се провери еквивалентността на автоматите M_1 и M_2, е достатъчно да се докаже, че симетричната разлика на езиците L(M_1) и L(M_2) е празна. За да направите това, на свой ред е достатъчно да конструирате автомат, който допуска тази разлика и да се уверите, че езикът, който допуска, е празен. Като цяло, проблемът с разпознаването, че езикът на държавната машина е празен, се нарича проблем с празнотата на държавната машина. За да се реши този проблем, е достатъчно да се намери множеството крайни състояния на автомата, които са достижими от началното състояние. Тъй като крайната машина е насочена графа, този проблем може да бъде решен, например, като се използва търсене в ширина. Език, разрешен от крайна машина, е празен, ако и само ако наборът от крайни състояния, достижими от първоначалното състояние, е празен. На практика е за предпочитане да се разпознае еквивалентността на крайните автомати с помощта на алгоритъм за минимизиране, но сега е важно да подчертаем, че фундаменталната възможност за решаване на проблема с еквивалентността следва от теорема 7.7 и нейните алгебрични следствия.
