Analiza lexicală. Limbaje obișnuite și mașini cu stări finite
prin numărul total de caractere ale alfabetului de simboluri și semne de operare și paranteze din intrarea r.Bază. Automate pentru expresiile de lungime 1: și sunt prezentate în figura următoare.
Orez. 5.1.
Rețineți că pentru fiecare dintre aceste trei automate, setul de stări finale constă dintr-o singură stare.
Etapa de inducție. Acum să presupunem că pentru fiecare expresie regulată de lungime = 1, cuvântul w poate fi împărțit în k subcuvinte: w=w 1 w 2 ... w k și atât. Pentru fiecare i= 1,... ,k cuvântul w i se traduce q 0 1 în q f 1 . Apoi, pentru cuvântul w din diagrama M există o cale
Prin urmare, . În schimb, dacă un cuvânt traduce q 0 în q f , atunci fie el există, fie este purtat de o cale care, trecând de la q 0 la q 0 1 și trecând apoi de mai multe ori pe calea de la q 0 1 la q f 1 și revenind de la q f 1 la q 0 1 prin -tranziție, în cele din urmă de la q f 1 prin -tranziție se termină în q f . Prin urmare un astfel de cuvânt.
Din teoremele 4.2 și 5.1 obținem direct
Corolarul 5.1. Pentru fiecare expresie regulată, se poate construi efectiv o mașină deterministă cu stări finite care recunoaște limbajul reprezentat de acea expresie.
Această afirmație este unul dintre exemplele de teoreme de sinteză: pe baza descrierii unei sarcini (limbaj ca expresie regulată), se construiește eficient un program (DFA) care o realizează. Este adevărat și invers - o teoremă de analiză.
Teorema 5.2. Pentru fiecare mașină cu stări finite deterministă (sau nedeterministă), este posibil să se construiască o expresie regulată care să reprezinte limbajul recunoscut de acea mașină.
Dovada acestei teoreme este destul de tehnică și dincolo de scopul cursului nostru.
Astfel, putem concluziona că clasa limbilor cu automate finite coincide cu clasa limbilor obișnuite. De acum înainte, o vom numi pur și simplu clasa de limbaje automate.
Automatul M r, care este construit în demonstrația teoremei 5.1
Definiții de bază Expresiile regulate din alfabetul Σ și mulțimile regulate pe care le denotă sunt definite recursiv după cum urmează: 1) – o expresie regulată care denotă o mulțime regulată; 2) e – expresie regulată care denotă o mulțime regulată (e); 3) dacă a Σ, atunci a este o expresie regulată care denotă o mulțime regulată (a); 4) dacă p și q sunt expresii regulate care denotă mulțimi regulate P și Q, atunci a) (p+q) este o expresie regulată care denotă P Q; b) pq – expresie regulată care denotă PQ; c) p* – expresie regulată care denotă P*; 5) nimic altceva nu este o expresie regulată.
Definiții de bază Prioritizare: * (iterație) – cea mai mare prioritate; concatenare; + (unire). Deci 0 + 10* = (0 + (1 (0*))). Exemple: 1. 01 înseamnă (01); 2. 0* – (0*); 3. (0+1)* – (0, 1)*; 4. (0+1)* 011 – înseamnă ansamblul tuturor lanțurilor alcătuite din 0 și 1 și care se termină cu lanțul 011; 5. (a+b) (a+b+0+1)* înseamnă mulțimea tuturor lanțurilor (0, 1, a, b)* începând cu a sau b.
Definiții de bază ale lemei: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Relația dintre RT și RM RM sunt limbi generate de RT. De exemplu: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Concatenare: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (balenă, pisică) sau după Lemele nr. 5 și nr. 6 k(u+o)t = balenă + pisică (balenă, pisică) . Iterație: x = a, x* X* = (e, a, aaa, …), adică x* = e + xxx + …
Legătura dintre RP și RM Iterația concatenării și unirii: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx + … Exemplu: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111… ). Unirea este comutativă: x + y = y + x Concatenarea nu este: xy ≠ yx
Comunicare între RM și RM Exemple de prioritate: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, aaa, aaaa, ...), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, …), (xy)* (e, xyxy, …), xy* (x, xyy, xyyy, …). Leme noi: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; etc.
Sisteme regulate de ecuații Ecuație cu coeficienți regulați X = a. X + b are o soluție (cel mai mic punct fix) a*b: aa*b + b = (aa* + e)b = a*b Sistem de ecuații cu coeficienți regulați: 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 Necunoscute – Δ = (X 1, X 2, …, Xn).
Sisteme regulate de ecuații Algoritm soluție (metoda Gauss): Pasul 1. Setați i = 1. Pasul 2. Dacă i = n, treceți la pasul 4. În caz contrar, scrieți ecuațiile pentru Xi sub forma Xi = αXi + β (β = β 0 + βi +1 Xi+1 + … + βn. Xn). Apoi, în partea dreaptă pentru ecuațiile Xi+1, ..., Xn, înlocuim Xi cu expresia regulată α*β. Pasul 3. Creșteți i cu 1 și reveniți la pasul 2. Pasul 4. Scrieți ecuația pentru Xn ca Xn = αXn + β. Treceți la pasul 5 (cu i = n). Pasul 5. Ecuația pentru Xi este Xi = αXi + β. Scrieți la ieșire Xi = α*β, în ecuațiile pentru Xi– 1, …, X 1, înlocuind α*β în loc de Xi. Pasul 6. Dacă i = 1, opriți, altfel micșorați i cu 1 și reveniți la pasul 5.
Transformarea DFA în RT Pentru DFA M = (Q, Σ, δ, q 0, F) compunem un sistem cu coeficienți regulați în care Δ = Q: 1. setați αij: = ; 2. dacă δ(Xi, a) = Xj, a Σ, atunci αij: = αij + a; 3. dacă Xi F sau δ(Xi,) = HALT, atunci αi 0: = e. După rezolvare, PV dorită va fi X 1 = q 0.
Conversia DFA în RV Exemplu: pentru un număr cu virgulă fixă obținem sistemul 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 Aici: s – semnul numărului, s = „+” + „–”; p – virgulă zecimală, p = "."; d – numere, d = „0” + „1” + … + „9”.
Conversia DFA în RT Soluție: 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. Din a treia ecuație: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). Din a patra ecuație: q 4 = dq 4 + e = d*.
Conversia DFA în RT Cursa inversă: 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). Astfel, acest DFA corespunde RT s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Să simplificăm: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Pentru o notație mai scurtă, puteți folosi iterația pozitivă aa* = a*a = a+: (s + e)(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)
Conversia DFA în RT Maparea graficului funcției de tranziție DFA la operații de bază cu expresii regulate: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
Conversia DFA în RT Combinații mai complexe de operații: 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*
Conversia DFA în RT Pentru 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
Programare RV Expresii regulate: Construit în multe limbaje de programare (PHP, Java. Script, ...); Implementat ca componente plug-in (de exemplu, clasa Regex pentru platforma .NET). Diferențele în formele de notație: x? = x + e x(1, 3) = x + xxx etc.
Programarea RT Constructe ale clasei Regex (System. Text. Regular. Expresii): Simbol Interpretarea secvenței de evacuare b Când este folosit între paranteze drepte, corespunde simbolului „←” (u 0008) t, r, n, a, f, v Tab (u 0009), retur car (u 000 D), linie nouă (u 000 A), etc. c. X Caracter de control (de ex. c. C este Ctrl+C, u 0003) e Escape (u 001 B) ooo Caracter ASCII în octal xhh Caracter ASCII în hexazecimal uhhhh Caracter Unicode Următorul caracter nu este un caracter RT special. Acest simbol trebuie folosit pentru a evada toate caracterele speciale. Exemplu (exemplul arată un model și un șir de căutare, potrivirile găsite sunt subliniate în șir): @"rnw+" – "rn. Există două linii aici."
Programarea RV Subseturi de simboluri. Orice caracter, cu excepția sfârșitului rândului (n) Orice caracter din set [^xxx] Orice caracter, cu excepția caracterelor din set Orice caracter din interval ] Scăderea unui set sau a unui interval din alt p(nume) Orice caracter specificat de Unicode categorie numită nume P (nume) Orice caracter, altul decât cele specificate de numele categoriei Unicode w Setul de caractere utilizat în specificarea identificatorilor W Setul de caractere neutilizat în specificarea identificatorilor s Spații S Toate, cu excepția spațiilor d Numerele D Exemple fără cifre : @". +" – "rn. Sunt ndouă linii"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p(Lu)" – "Luminile orașului"; // Lu – majuscule @"P(Lu)" – "Oraș"; @"p(Is. Chirilic)" – "ha. OS"; //Este. litere chirilice – ruse
Programare PB Ancoră ^, A La începutul liniei $, Z La sfârșitul rândului sau înainte de caracterul „n” de la sfârșitul rândului z La sfârșitul liniei G Unde se termină potrivirea anterioară b Limită cuvânt B Orice poziție care nu este la granița unui cuvânt Exemple: @ „G(d)” – „(1)(3)(5)(9)”; // trei meciuri (1), (2) și (3) @"bnS*ionb" – "donație națiune"; @"Bendw*b" – „sfârșitul trimite îndurer creditor”.
Programarea operațiunilor RT (cuantificatoare) *, *? Iterație +, +? Iterație pozitivă? , ? ? Zero sau o potrivire (n), (n)? Exact n se potrivește (n, ), (n, )? Cel puțin n potrivește (n, m), (n, m)? De la n la m se potrivește Exemple (primii cuantificatori sunt lacomi, caută cât mai multe elemente, al doilea sunt leneși, caută cât mai puține elemente): @"d(3, )" – "888 -5555 "; @"^d(3)" – "913 -913"; @"-d(3)$" – "913 -913"; @"5+? 5" – "888 -5555"; // trei meciuri - 55, 55 și 55 @"5+5" - "888 -5555".
Programare RV Grupare () Un grup care primește automat un număr (? :) Nu salvați grupul (?) sau (? „nume”) Dacă se găsește o potrivire, este creat un grup numit (?) sau Ștergeți un grup definit anterior grup și (? „nume - nume”) salvarea într-un grup nou a unui subșir între un grup definit anterior și un grup nou (? imnsx:) Activează sau dezactivează oricare dintre cele cinci (? –imnsx:) opțiuni posibile dintr-un grup: i – nu ține seama de majuscule; s – o linie (atunci „.” este orice caracter); m – modul cu mai multe linii („^”, „$” – începutul și sfârșitul fiecărei linii); n – nu captați grupuri fără nume; x – excludeți spațiile fără escape din model și includeți comentarii după semnul numeric (#) (? =) O declarație anticipată pozitivă de lungime zero
Programare RT (? !) Declarație anticipată de lungime zero negativă (?) Parte nereturnabilă (lacomă) a unei expresii Exemple: @"(an)+" – "ananale banane"; @"an+" – "ananale de banane"; // compara, trei potriviri - an, an and ann @"(? i: an)+" - "ba. NAnas anals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://site/presentation/-112203859_437213351/image-24.jpg" alt="RV Număr de legături de programare Link către grupul k Link către grupul numit Exemple: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
Programarea substituțiilor RV $number Înlocuiește partea din șir corespunzătoare grupului cu numărul specificat $(nume) Înlocuiește partea din șir corespunzătoare grupului cu numele specificat $$ Înlocuiește $ $& Înlocuiește cu o copie a întregului potrivire $` Înlocuiește textul șirului de intrare până când se potrivește cu $" Înlocuiește textul liniilor de intrare după potrivirea $+ Înlocuiește ultimul grup capturat $_ Înlocuiește întregul rând Comentarii (? #) Comentariu în linie # Comentariu la sfârșitul rândului
Programare RT Rezultatele Regex: Regex Matches() Match. Grupuri de potrivire de colecție(). Captură de grup de colecție() Captură. Capturi de colecție()
Exemplu de programare RV în C++ CLI (Visual C++/CLR/CLR Console Application): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Potrivire ^m = r-> Potrivire (L"123 456"); int potrivire. Count = 0; while (m->Success) ( Consolă: : Write. Line(L"Match (0)", ++match. Count); for (int i = 1; i Grupuri->Număr; i++) ( Grup ^g = m->Grupuri[i]; Consolă: : Scriere. Linie (L" Grup (0) = "(1)"", i, g-> Valoare ); pentru (int j = 0; j Capturi->Număr; j++) ( Captură ^c = g->Capturi[j]; Consolă: : Scriere. Linie(L" Captură (0) = "(1)" , poziție = (2), lungime = (3)", j, c, c->Index, c->Lungime); ) ) m = m->Next. Potrivire(); ) returnează 0; ) Sistem: : Text : : Obisnuit. Expresii
Activarea acțiunilor și găsirea erorilor Limitarea numărului de cifre semnificative dintr-un număr: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = d s + e = s? = (+|-)? pd* + e = (pd*)? = (.d*)? @"(+|-)? (. d+|d+(. d*)?)" sau @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = regex nou (@"^(+|-)? (. (? "cifra"d)+|(? "cifra"d)+(. (? "cifra"d)*)?)$"); Potriviți m = r. Potrivire ("+1. 23456789"); dacă (m. Succes) ( Grupul g = m. Grupuri[„cifră”]; dacă (g. Capturi. Număr
Activarea acțiunilor și găsirea erorilor Determinarea poziției erorii: Regex r = regex nou(@"(+|-)? (. (? "cifră"d)+|(? "cifră"d)+(. (? "cifră" d )*)?)"); șir str = "+1. 2345!678"; Potriviți m = r. Potrivire(str); if (m. Succes) ( Grup g = m. Grupuri[„cifră”]; dacă (g. Capturi. Număr 0) Consolă. Scriere. Linie(„Eroare la poziția 1: caracter neașteptat „(0)””, str ); altfel dacă (m. Lungime
Activarea acțiunilor și căutarea erorilor Determinarea poziției erorii: 1. prima poziție a lanțului de intrare (1), dacă prima potrivire nu începe de la poziția Index = 0; 2. poziția care urmează ultimului meci (meci. Lungime + 1), dacă nu se potrivește cu ultima poziție a lanțului de intrare; 3. poziţia primului decalaj dintre potriviri (match[i]. Index + potrivire[i]. Lungime + 1), dacă caracterul care urmează meciului precedent nu este primul caracter al meciului următor.
Index) pauză; indice = m[i]. Index + m[i]. Lungime; ) Consolă. Scrie. Line("Eroare la poziția (0) "(1)"", index + 1, str); ) „abc. xyz. pqr" – corect; „+abc. xyz. pqr” – eroare în poziția 1 (“+”); „abc. xyz. pqr! – eroare în poziţia 12 (“!”); „abc. xyz!. pqr" – eroare în poziția 8 (“!”).
Activarea acțiunilor și căutarea erorilor Dar! „abc. xyz. +pqr” – eroare la poziția 8 (“.”). Opțiune nouă de șablon: @"w+(. w+)*(. (? !$))? " Validare: "abc. xyz. +pqr” – eroare în poziția 9 (“+”); „abc. xyz. pqr. " – eroare în poziția 12 (".").
Definiții echilibrate: „(? „x”)” adaugă un element la colecția numită „x”; „(? „-x”)” elimină un element din colecția „x”; „(? (x)(? !))” verifică dacă nu au mai rămas elemente în colecția „x”. Limbajul L care descrie operatorii imbricați Pascal „begin end; ": @"^s*((? "începe+)+(? "-început"se termină*; s*)+)*(? (începe)(? !))$".
Este mai convenabil să descrii vocabularul unei limbi sub formă de expresii regulate și să recunoști limba folosind CA. Prin urmare, este important să puteți converti definițiile limbajului sub formă de expresii regulate într-o definiție sub forma unui CA. Această transformare a fost propusă de Kenneth Thompson.
Mașina cu stări finite este cinci (S, S, d, S 0 , F)
S este un set finit de stări.
S este un set finit de semnale de intrare valide.
d - funcţia de tranziţie. Ea reflectă mulțimea Sx(SÈ(e)) în mulțimea de stări ale unui automat finit nedeterminist. Pentru un automat determinist, funcția de tranziție reflectă setul SxS în setul de stări ale automatului. Cu alte cuvinte, în funcție de stare și simbolul de intrare, d determină noua stare a mașinii.
S 0 - starea inițială a automatului finit, S 0 О S.
F este mulțimea stărilor finale ale automatului, F О S.
Funcționarea unei mașini cu stări finite este o succesiune de pași. Pasul este determinat de starea mașinii și de simbolul de intrare. Pasul în sine constă în schimbarea stării mașinii și citirea următorului simbol al secvenței de intrare.
Există următoarele reguli pentru convertirea expresiilor regulate într-o mașină de stări.
1 Expresia regulată „e” este transformată într-un automat cu două stări și o e-tranziție între ele (Figura 1).
Figura 1. – Mașină automată pentru e-tranziție
2 O expresie regulată dintr-un caracter „a” este convertită într-un automat finit de două stări și o tranziție între ele pe baza semnalului de intrare a (Figura 2).
Figura 2. – Mașină automată pentru deplasare prin simbolul a
3 Să existe o expresie regulată rs și mașini cu stări finite pentru expresia r și expresia s au fost deja construite. Apoi două mașini sunt conectate în serie. Figura 3 prezintă automatele originale pentru limbile r și s. Figura prezintă un automat pentru recunoașterea concatenării acestor limbi.
Mașină pentru r Mașină pentru s
Figura 3. – Automate inițiale
Figura 4. – Mașină de concatenare a limbii
4 Fie o expresie regulată r | s și mașinile cu stări finite au fost deja construite pentru expresia r și expresia s (Figura 3). Atunci automatul rezultat trebuie să aibă o alternativă la executarea unuia dintre cele două automate. Adică un automat pentru expresia r | s pentru automate pentru r și s din figura 3 are forma prezentată în figura 5.
Figura 5. – Mașină automată pentru combinarea limbilor
5 Să existe o expresie regulată r* pentru automatul finit construit r. În acest caz, sunt introduse două stări noi pentru a face posibilă ocolirea expresiei automatului r și, de asemenea, introducerea unei e-tranziții între stările finală și inițială pentru a face posibilă repetarea automatului r de mai multe ori. Dacă pentru expresia regulată r este construit un automat similar cu figura 3, atunci expresia regulată r* corespunde automatului finit prezentat în figura 6.
Setări
Conform teoremei lui Kleene, orice expresie regulată puteți asocia o mașină finită, care este un model formal al algoritmului de recunoaștere a lexemelor notate printr-o expresie regulată dată. În termeni cei mai generali, o mașină de stat-recunoaștetorul este determinat de un set finit de stări caracteristice ale fluxului de intrare și tranziții între ele. O schimbare de stare are loc atunci când simbolurile fluxului de intrare sunt primite de la un alfabet dat în conformitate cu funcția de tranziție, care determină posibile stări ulterioare pe baza simbolului de intrare și a stării curente. Dintre stările posibile se remarcă cea inițială(iniţială) și finală(permițând) stări în care recunoașterea automată finită se poate afla, respectiv, la începutul și finalizarea procesării token-ului fluxului de intrare. Dacă secvența de intrare de simboluri poate genera o secvență de tranziții care poate transfera mașina cu stări finite din starea inițială la una din stările finale, atunci este considerată admisă și aparține mulțimii obișnuite recunoscute de aceasta.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
tabelul 1
| 0 | 1 | |
| Î1 | Î4 | Q2 |
| Q2 | Q3 | Î1 |
| Q3 | Q2 | Î4 |
| Î4 | Î1 | Q3 |
Coloanele tabelului de tranziție indică caracterele alfabetului de intrare, iar rândurile corespund stărilor curente ale DFA. Elementele fiecărei linii indică stările DFA, la care trebuie să treacă de la starea curentă la primirea caracterelor corespunzătoare ale alfabetului de intrare. În special, din prima linie a acestui tabel de tranziție rezultă că primirea simbolurilor 0 și 1 în starea inițială Q1 traduce DFA la stările Q4 și, respectiv, Q2.
Când recunoașteți o secvență de intrare folosind tabelul de tranziție, este ușor să urmăriți modificările în starea DFA pentru a determina dacă una dintre stările permisive este atinsă sau nu. În special, pentru vectorul binar 01001000 cu un număr par de zerouri și unu, DFA considerat generează următoarea secvență de tranziții, în care fiecare tranziție este etichetată de simbolul alfabetului de intrare care o provoacă:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Această secvență de tranziții se termină cu starea de admitere Q1, prin urmare, vectorul binar 01001000 aparține mulțimii obișnuite recunoscute de DFA consideratși satisface expresia regulată de mai sus.
În concluzie, trebuie remarcat faptul că metoda informală de construcție considerată
Pentru studiul suplimentar al proprietăților automatelor finite și, în special, pentru rezolvarea problemei de sinteză, următoarea teoremă este importantă.
Teorema 7.7 (teorema determinării). Pentru orice automat finit, se poate construi un automat finit determinist echivalent.
Pentru a demonstra teorema, este necesar, în primul rând, să descriem algoritmul de construire a unui automat finit determinist din cel original; în al doilea rând, să justifice acest algoritm prin demonstrarea riguroasă că produce într-adevăr o mașină de stări care este deterministă și echivalentă cu cea originală. Prezentăm aici doar algoritmul pentru construirea unui automat determinist.
Transformarea unui automat finit arbitrar într-unul determinist echivalent se realizează în două etape: în primul rând, arcele cu eticheta \lambda sunt îndepărtate, apoi se realizează determinarea în sine.
1. Eliminarea tranzițiilor λ (arce etichetate \lambda).
Pentru a trece de la automatul finit original M=(V,Q,q_0,F,\delta) la automatul finit echivalent M"=(V,Q",q_0,F",\delta") fără tranziții λ, se este suficient în original face următoarele transformări în graficul M.
A. Toate stările, cu excepția celei inițiale, în care intră doar arce cu eticheta \lambda, sunt șterse; definindu-se astfel multimea Q" a automatului finit M". Este clar că Q"\subseteq Q. În același timp, presupunem că starea inițială rămâne aceeași.
b. Mulțimea de arce ale automatului finit M" și etichetele lor (prin urmare funcția de tranziție M" ) este definită astfel: pentru oricare două stări p,r\in Q",~ p\to_(a)r apare dacă și numai dacă a \în V și în graficul M este valabil unul din două lucruri: fie există un arc de la p la r a cărui etichetă conține simbolul a, fie există o stare q astfel încât p\Rightarrow_(\lambda)^( +)q și q\ to_(a)r În acest caz, vârful q, în general, poate să nu aparțină mulțimii Q", adică. poate dispărea la trecerea la automatul M" (Fig. 7.11). Dacă q\in Q" , atunci, firesc, arcul (q,r) se va păstra în M" iar simbolul a va fi unul dintre simboluri aparţinând etichetei acestui arc (Fig. 7.12).
Astfel, în M" sunt stocate toate arcele M ale căror etichete sunt diferite de \lambda și care conectează o pereche (vârfurile) de stări din mulțimea Q" (neștersă conform părții a). În plus, pentru orice triplu de stări p,q,r (nu neapărat diferit!), astfel încât p,r\in Q" și există o cale de lungime diferită de zero de la p la q, a cărei etichetă este egală la \lambda (adică calea prin tranziții λ), și un arc duce de la q la r, a cărui etichetă conține simbolul a al alfabetului de intrare, în M" se construiește un arc de la p la r, eticheta de care conţine simbolul a (vezi Fig. 7.11).
V. Mulțimea stărilor finale F" ale automatului finit M" conține toate stările q\în Q", adică stările automatului finit M care nu sunt șterse conform paragrafului a, pentru care q\Rightarrow_(\lambda)^(\ ast) deține q_f pentru unele q_f\în F (adică fie starea q însăși este starea finală a automatului finit M, fie o cale de lungime diferită de zero duce de la acesta de-a lungul arcurilor etichetate \lambda către una dintre stările finale ale automat finit M) (Fig. 7.13) .
2. Determinarea în sine.
Fie M=(Q,V,q_0,F,\delta) un automat finit fără λ-tranziții. Să construim un automat finit determinist M_1 echivalent cu M.
Acest automat finit este definit în așa fel încât mulțimea lui de stări să fie mulțimea tuturor submulților din mulțimea de stări a automatului finit M. Aceasta înseamnă că fiecare stare individuală a automatului finit M_1 este definită ca un anumit subset al setului de stări ale automatului finit M. În acest caz, starea inițială a noii mașini cu stări finite (adică M_1) este o submulțime singleton care conține starea inițială a vechii mașini cu stări finite (adică M), iar stările finale ale noii mașini cu stări finite sunt toate astfel de subseturi. Q care conțin cel puțin un vârf final al automatului finit original M.
De acum înainte, permițând o oarecare libertate de exprimare, vom numi uneori stările automatului finit M_1 seturi de stări. Este important, totuși, să înțelegem clar că fiecare astfel de set de stări este o stare separată a unui nou automat finit, dar nu un set al stărilor sale. În același timp, pentru automatul finit original („vechi”) M acesta este tocmai mulțimea stărilor sale. Figurat vorbind, fiecare subset de stări ale vechiului automat finit este „prăbușit” într-o stare a noului automat finit*.
*În mod formal, ar trebui să definim mulțimea Q_1 ca o mulțime care este în corespondență unu-la-unu cu mulțimea 2^Q, dar este încă mai convenabil pentru noi să presupunem că Q_1 coincide cu 2^Q - la urma urmei, set de stări ale unui automat finit poate fi orice mulțime finită nevidă.
Funcția de tranziție a noului automat finit este definită astfel încât de la setul de stări S prin simbolul de intrare a automatul finit M_1 trece la setul de stări, care este uniunea tuturor mulțimilor de stări ale vechiului automat finit în care acest vechi automat finit poartă simbolul a din fiecare set de stări S. Astfel, automatul finit M_1 este determinist prin construcție.
Descrierea verbală de mai sus poate fi tradusă în formule după cum urmează: construim o mașină finită M_1 astfel încât
M_1=(Q_1,V,\(q_0\),F_1,\delta_1) , unde
\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(cazuri)
Să fim atenți la faptul că printre stările noului automat finit există o stare \varnothing , și, conform (7.8), \delta_1(\varnothing,a)=\varnothing pentru orice simbol de intrare a . Aceasta înseamnă că, odată într-o astfel de stare, mașina de stări M_1 nu o va părăsi. În general, orice stare q a unui automat finit astfel încât pentru orice simbol de intrare a avem \delta(q,a)=q se numește stare absorbantă a automatului finit. Astfel, starea \varnothing a mașinii deterministe cu stări finite M_1 este absorbantă. De asemenea, este util să rețineți că \delta_1(S,a)=\varnothing if și numai dacă pentru fiecare q\in S (stări ale vechii mașini cu stări finite din mulțimea stărilor S ) \delta(q,a)= \varnothing , adică de ex. în graficul M, niciun arc nu iese din fiecare astfel de stare q, marcată cu simbolul a.
Se poate dovedi că automatul finit obținut folosind un astfel de algoritm este echivalent cu cel original.
Exemplul 7.9. Să determinăm automatul finit prezentat în Fig. 7.14.
Un automat finit echivalent fără tranziții λ este prezentat în Fig. 7.15. Rețineți că vârful q_2 dispare, deoarece în el intră doar arce „goale”.
Pentru a determina automatul rezultat, nu este deloc necesar să notăm toate stările sale 2^3=8, dintre care multe nu pot fi accesibile din starea inițială \(q_0\) . Pentru a obține stări care sunt accesibile din \(q_0\), și numai ele, vom folosi așa-numita metodă pulling.
Această metodă poate fi descrisă în general după cum urmează.
În automatul finit inițial (fără arce goale) definim toate seturile de stări care sunt accesibile din cel inițial, adică. pentru fiecare simbol de intrare a găsim mulțimea \delta(q_0,a) . Fiecare astfel de set din noul automat este o stare direct accesibilă din cea inițială.
Pentru fiecare dintre seturile de stări definite S și fiecare simbol de intrare a, găsim mulțimea \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom( A)^( .))). Toate stările obținute la acest pas vor fi stări ale unui nou automat (determinist), accesibil de la vârful inițial de-a lungul unui drum de lungime 2. Repetăm procedura descrisă până când nu apar noi stări de set (inclusiv cea goală!). Se poate arăta că aceasta produce toate stările automatului finit M_1 care sunt accesibile din starea inițială \(q_0\) .
Pentru mașina cu stări finite din fig. 7.15 avem:
\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(aliniat)
Deoarece nu au apărut noi seturi de stări, procedura de „tragere” se termină aici și obținem graficul prezentat în Fig. 7.16.
Adăugarea obișnuită a limbiiUna dintre consecințele teoretice importante ale teoremei determinării este următoarea teoremă.
Teorema 7.8. Complementul unei limbi obișnuite este un limbaj obișnuit.
Fie L o limbă obișnuită în alfabetul V. Atunci complementul limbajului L (ca un set de cuvinte) este limba \overline(L)=V^(\ast)\setminus L .
Conform teoremei 7.7, pentru un limbaj regulat L se poate construi un automat finit determinist M care admite L. Deoarece într-un automat determinist de la fiecare vârf pentru fiecare simbol de intrare este definită o tranziție la exact un vârf, atunci oricare ar fi lanțul x în alfabetul V, există o cale unică pentru acesta în M, începând din starea inițială în care se citește lanțul x. Este clar că lanțul x este permis de automatul M , adică x\in L(M) , dacă și numai dacă ultima stare a căii specificate este finală. Rezultă că lanțul x\notin L(M) dacă și numai dacă ultima stare a căii specificate nu este finală. Dar avem nevoie doar de un automat finit M" care admite un lanț x dacă și numai dacă nu este permis de automatul finit original M. În consecință, transformând fiecare stare finală a lui M într-o stare nefinală și invers, obținem o automat determinist care admite adăugarea limbajului L .
Teorema dovedită ne permite să construim un automat finit care nu admite un anumit set de lanțuri, folosind următoarea metodă: mai întâi construim un automat care admite un anumit set de lanțuri, apoi îl determinăm și mergem la automat pentru adunare ca indicat în demonstraţia teoremei 7.8.
Exemplul 7.10. A. Să construim un automat finit care acceptă toate lanțurile din alfabetul \(0;1\), cu excepția lanțului 101.
Mai întâi, să construim un automat finit care permite un singur lanț 101. Acest automat este prezentat în Fig. 7.17.
Acest automat este cvasi-determinist, dar nu determinist, deoarece nu este complet definit. Să o determinăm și să obținem un automat finit echivalent determinist prezentat în Fig. 7.18.
Și, în final, trecând la adăugarea (și redenumirea stărilor), obținem automatul prezentat în Fig. 7.19.
Rețineți că în automatul rezultat toate nodurile, cu excepția vârfului s_3, sunt finale.
De asemenea, rețineți că trecerea la complement, care este discutată în demonstrația teoremei 7.8, poate fi efectuată numai într-un automat determinist. Dacă ar fi să schimbăm rolurile vârfurilor finale și nefinale în automatul prezentat în Fig. 7.17, atunci am obține un automat care admite limbajul \(\lambda,1,10\) , care nu este - așa cum se poate imagina cu ușurință - mulțimea tuturor lanțurilor, altele decât lanțul 101.
Rețineți, de asemenea, că mașina cu stări finite din Fig. 7.19 permite toate șirurile care conțin o apariție a șirului 101, dar nu se potrivesc cu acel șir în sine. Iată, de exemplu, lanțul care poartă calea 1011: s_0,s_1,s_2,s_3,t.
b. Să construim un automat finit care acceptă toate lanțurile din alfabetul \(0;1\) cu excepția celor care conțin o apariție a lanțului 101. Să considerăm un limbaj L, fiecare lanț al căruia conține o apariție a lanțului 101. Poate fi definit după cum urmează:
L=(0+1)^(\ast)101(0+1)^(\ast).
Trebuie să construim un automat care să completeze limbajul L.
În acest caz, folosind expresia regulată direct, este ușor de construit un automat finit care acceptă limbajul L (Fig. 7.20).
Apoi vom efectua determinarea folosind metoda „pull”. Rezultatul determinării este prezentat în Fig. 7.21.
Pentru a rezolva complet problema, tot ce rămâne este în Fig. 7.21 schimba rolurile vârfurilor finale și non-finale (Fig. 7.22).
V. Să discutăm ideea de a construi un automat finit care să permită acele și numai acele lanțuri din alfabet \(0;1\) care nu încep cu lanțul 01 și nu se termină cu lanțul 11 (adică lanțuri ale forma 01x și lanțurile de tip y11 nu sunt permise, indiferent de ce au fost lanțuri x,y\in\(0;1\) ).
În acest caz, complementul limbajului pentru care este necesar să se construiască un automat finit este mulțimea tuturor astfel de lanțuri de zerouri și cele care încep cu lanțul 01 sau se termină cu lanțul 11. Un automat care permite acest set de chains este construit ca un automat pentru combinarea 01(0+1)^(\ ast)+(0+1)^(\ast)11 în același mod ca cel descris în demonstrația teoremei lui Kleene (vezi Teorema 7.6).
Din proprietatea că clasa limbajelor regulate este închisă în raport cu complementul (vezi Teorema 7.8) rezultă imediat că această clasă este închisă în raport cu intersecția, diferența teoretică și simetrică.
Corolarul 7.3. Pentru oricare două limbi obișnuite L_1 și L_2 următoarele afirmații sunt adevărate:
1) intersecția lui L_1\cap L_2 este regulată;
2) diferența L_1\setminus L_2 este regulată;
3) diferența simetrică L_1\vartriangle L_2 este regulată.
Valabilitatea afirmațiilor decurge din identitățile:
\begin(aliniat) &(\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(aliniat)
În primul rând, rezultatele obținute ne permit să afirmăm că clasa limbajelor regulate în ceea ce privește operațiile de unire, intersecție și adunare este o algebră booleană, în care unitatea este limba universală, iar zero este limbajul gol. În al doilea rând, aceste proprietăți algebrice ale familiei de limbaje regulate ne permit să rezolvăm problema importantă a recunoașterii echivalenței a două automate finite arbitrare.
Conform Definiției 7.10, mașinile cu stări finite sunt echivalente dacă limbajele pe care le acceptă sunt aceleași. Prin urmare, pentru a verifica echivalența automatelor M_1 și M_2, este suficient să se demonstreze că diferența simetrică a limbajelor L(M_1) și L(M_2) este goală. Pentru a face acest lucru, la rândul său, este suficient să construiți un automat care să admită această diferență și să vă asigurați că limbajul pe care îl admite este gol. În general, problema recunoașterii faptului că limbajul unei mașini de stări este goală se numește problema vidului mașinii de stări. Pentru a rezolva această problemă, este suficient să găsim setul de stări finale ale automatului care sunt accesibile din starea inițială. Deoarece o mașină cu stări finite este un grafic direcționat, această problemă poate fi rezolvată, de exemplu, folosind căutarea pe lățime. Un limbaj permis de o mașină cu stări finite este gol dacă și numai dacă setul de stări finale accesibile din starea inițială este gol. În practică, este de preferat să recunoaștem echivalența automatelor finite folosind un algoritm de minimizare, dar acum este important pentru noi să subliniem că posibilitatea fundamentală de rezolvare a problemei de echivalență rezultă din Teorema 7.7 și din consecințele ei algebrice.
