Analiza lexicală. Limbaje obișnuite și automate finite
prin numărul total de caractere ale alfabetului de simboluri și semne de operații și paranteze din înregistrarea r .Bază. Automate pentru expresiile de lungime 1: și sunt prezentate în figura următoare.
Orez. 5.1.
Rețineți că fiecare dintre aceste trei automate are set de stări finale constă dintr-un singur stat.
etapa de inducție. Să presupunem acum că pentru fiecare expresie uzuala lungime<= k
построен соответствующий
НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное
expresie uzuala r de lungime k+1 . În funcție de ultima operație, poate avea una din trei forme: (r 1 + r 2), (r 1 r 2) sau (r 1) * . Fie și să fie NFA care recunosc limbajele L r1 și, respectiv, L r2. Fără a pierde generalitatea, vom presupune că au stări diferite: 
.
Apoi NFA, a cărui diagramă este prezentată în Fig. 5.2, recunoaște limba.
Orez. 5.2.
Această mașină are set de state, unde q 0 este o stare inițială nouă, q f este o stare finală nouă (unica!), iar programul include programe automate M 1 și M 2 și patru comenzi noi de tranziție: . În mod evident, limbajul recunoscut de NFA M include toate cuvintele din L ( M 1 ) și din L ( M 2 ). Pe de altă parte, fiecare cuvânt ia q 0 la q f , iar după primul pas calea care îl poartă trece prin q 0 1 sau q 0 2 . Deoarece stările M 1 și M 2 nu se intersectează, atunci în primul caz această cale poate ajunge la q f numai printr-o -tranziție de la q f 1 și apoi 
. În mod similar, în al doilea caz.
Pentru expresie, diagrama NFA care recunoaște limbajul L r este prezentată în figura următoare.
Orez. 5.3.
Această mașină are set de state 
, starea inițială q 0 = q 0 1 , starea finală q f =q f 2 , iar programul include programe automate M 1 și M 2 și o nouă instrucțiune - trecerea de la starea finală M 1 la starea inițială M 2 , adică. . Aici este, de asemenea, evident că orice cale de la q 0 = q 0 1 la q f = q f 2 trece printr-o -tranziție de la q f 1 la q 0 2 . Prin urmare, orice cuvânt permis de M este o concatenare a unui cuvânt din L M1 ) cu un cuvânt din L M2 ) , iar orice concatenare a unor astfel de cuvinte este permisă. Prin urmare, NFA M recunoaște limba .
Fie r = r 1 * . Diagrama NFA care recunoaște limbajul L r =L r1* = L M1 * este prezentată în fig. 5.3.
Orez. 5.3.
Această mașină are set de state, unde q 0 este o stare inițială nouă, q f este o stare finală nouă (unica!), iar programul include programul automat M 1 și patru comenzi noi de tranziție: . Evident, . Pentru un cuvânt care nu este gol w, prin definiția iterației 
pentru unele k >= 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 mapează q 0 1 la 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 calea q 0 1 prin -tranziție, eventual din 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 toată lumea expresie uzuala se poate construi eficient un automat finit determinist care să recunoască limbajul reprezentat de această expresie.
Această afirmație este un exemplu teoreme de sinteză: conform descrierii sarcinii (limbaj ca expresie uzuala) un program (DFA) care îl execută este construit eficient. Este adevărat și invers - teorema analizei.
Teorema 5.2. Pentru fiecare automat finit determinist (sau nedeterminist), se poate construi expresie uzuala, care reprezintă limbajul recunoscut de acest automat.
Dovada acestei teoreme este destul de tehnică și depășește scopul cursului nostru.
Astfel, putem concluziona că clasa de limbaje automate finite coincide cu clasa limbi obișnuite. În cele ce urmează, îl 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 este o expresie regulată care denotă o mulțime regulată (e); 3) dacă a Σ, atunci a este o expresie regulată care denotă mulțimea 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 este o expresie regulată care denotă PQ; c) p* este o 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ă mulțimea tuturor șirurilor compusă din 0 și 1 și care se termină în șirul 011; 5. (a+b) (a+b+0+1)* înseamnă mulțimea tuturor șirurilor (0, 1, a, b)* începând cu a sau b.
Principalele definiții ale Lemei: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5 ) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Comunicarea 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 prin Lemele nr. 5 și nr. 6 k(u+o)m = balenă + pisică (balenă, pisică) . Iterație: x = a, x* X* = (e, a, aaa, …), adică x* = e + xxx + …
Relația dintre RT ș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
Relația dintre RT și PM 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 \u003d α 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 ca 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 substituind α*β î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 RW Pentru DFA M = (Q, Σ, δ, q 0, F) compunem un sistem cu coeficienți regulați în care Δ = Q: 1. setăm αij: = ; 2. dacă δ(Xi, a) = Xj, a Σ, atunci αij: = αij + a; 3. dacă Xi F sau δ(Xi,) = HALT, atunci αi 0: = e. După rezolvarea RV dorită va fi X 1 = q 0.
Conversia DFA în RW 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 este semnul numărului, s = "+" + "–"; p – virgulă zecimală, p = "."; d - numere, d = "0" + "1" + ... + "9".
Conversie DFA în RW 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 \u003d dq 3 + pq 4 + e \u003d d * (pq 4 + e). Din a patra ecuație: q 4 = dq 4 + e = d*.
Convertiți DFA în RW 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 RE s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Pentru a simplifica: 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+)
Transformarea DFA în RT Maparea graficului funcției de tranziție DFA la operațiile 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*
Conversie DFA în RW Pentru RW (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
Expresii regulate de programare în timp real: încorporat în multe limbaje de programare (PHP, Java. Script, …); Implementat ca plug-in-uri (de exemplu, clasa Regex pentru platforma .NET). Diferențe în formele de scriere: x? = x + e x(1, 3) = x + xxx etc.
RT Programming Regex Class Constructs (System.Text.Regular.Expressions): Interpretarea secvenței de evadare a caracterelor b Când este folosit între paranteze drepte, se potrivește caracterul „←” (u 0008) t, r, n, a, f, v Tab (u 0009), întoarcere transport (u 000 D), linie nouă (u 000 A), etc. c. X Caracter de control (de exemplu, c. C este Ctrl+C, u 0003) e Escape (u 001 B) ooo Caracter octal ASCII xhh Caracter hex ASCII uhhhh Caracter Unicode Următorul caracter nu este un caracter PB special. Toate caracterele speciale trebuie să fie evadate cu acest caracter. Exemplu (în exemplu sunt date modelul și șirul de căutare, potrivirile găsite în șir sunt subliniate): @"rnw+" – "rn. Sunt n două șiruri aici" .
Programarea RT Subseturi de caractere. Orice caracter cu excepția sfârșitului șirului (n) Orice caracter din set [^xxx] Orice caracter, cu excepția caracterelor din set Orice caracter din interval ] Scădeți un set sau un interval din alt p(nume) Orice caracter specificat de Unicode categorie numită nume P (nume) Orice caracter, altul decât cele specificate de categoria Unicode numită nume w Set de caractere utilizate în specificarea identificatorilor W Setul de caractere neutilizate în specificarea identificatorilor s Spații S Orice cu excepția spațiilor d Cifre D Nu cifre Exemple: @ ". +" – "rn. Există n două linii aici"; @"+" - "0xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" - "0xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0xabcfx"; @"p(Lu)" - "Luminile orașului"; // Lu - litere mari @"P(Lu)" - "Oraș"; @"p(Is. Chirilic)" - "ha. OS"; // Este. litere chirilice - ruse
PB Ancoră de programare ^, A La începutul șirului $, Z La sfârșitul șirului sau până la caracterul „n” la sfârșitul șirului z La sfârșitul șirului G Unde s-a încheiat potrivirea anterioară b Cuvânt granița B Orice poziție care nu este pe 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 potriviri 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 RT Grupare () Grupul alocat automat un număr (?:) Nu salvați grupul (?) sau (? „nume”) Dacă se găsește o potrivire, creați un grup numit (?) sau Ștergeți un grup definit anterior și (? „nume-nume”) salvează în noul grup un subșir între grupul definit anterior și noul grup (? imnsx:) Activează sau dezactivează oricare dintre cele cinci (? -imnsx:) opțiuni posibile din grup: i - caz insensibil; s este o linie (atunci "." este orice caracter); m – modul multilinie (“^” , “$” – începutul și sfârșitul fiecărei linii); n - nu capta grupuri nenumite; x - excludeți spațiile fără escape din model și includeți comentarii după semnul numeric (#) (?=) Aserțiune anticipată pozitivă de lungime zero
Programare RE (? !) Afirmație anticipată negativă de lungime zero (?) Parte nereturnabilă (lacomă) a expresiei Exemple: @"(an)+" – "ananale bananelor"; @"an+" – "ananale de banane"; // compara, trei potriviri - an, an and ann @"(? i: an)+" - "ba. NAnas anals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://website/presentation/-112203859_437213351/image-24.jpg" alt="(!LANG:Programming RT Număr de referință Referință grup k Referință grup numit Exemple: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
Substituții de programare RT $număr Î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 potriviți $` Înlocuiți textul șirului de intrare până la se potrivește $" Înlocuiți textul liniei de intrare după potrivirea $+ Înlocuiți ultimul grup capturat $_ Înlocuiți întregul rând Comentarii (? #) Comentariu în linie # Comentariu la sfârșitul rândului
Rezultatele programării RT ale Regex: Regex Matches() Match. Grupuri de potrivire de colecție(). Captură de grup de colecție() Captură. Capturi de colecție()
Exemplu de programare RT î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) ( Consola: : 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ă: : Write.Line(L" Capture(0) = "(1)" , poziție = (2), lungime = (3)", j, c, c->Index, c->Lungime); ) ) m = m->Next. Potrivire(); ) returnează 0; ) Sistem: : Text : :Obisnuit. expresii
Includerea acțiunilor și căutarea erorilor Limitarea numărului de cifre semnificative dintr-un număr: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = ds + 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 unei erori: Regex r = regex new(@"(+|-)? (. (? "cifră"d)+|(? "cifră"d)+(. (? " cifra "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 șirului de intrare (1), dacă prima potrivire nu începe de la poziția Index = 0; 2. poziția care urmează ultimei potriviri (match. Lungime + 1), dacă nu se potrivește cu ultima poziție a șirului de intrare; 3. poziția primei pauze între meciuri (meci[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" este corect; + abc. xyz. pqr" - eroare în poziția 1 ("+"); „abc. xyz. pqr!" – eroare în poziţia 12 (“!”); „abc. xyz!. pqr" - eroare la poziția 8 ("!").
Includerea acțiunilor și căutarea erorilor Dar! „abc. xyz. +pqr" - eroare la poziția 8 ("". "). Varianta nouă de model: @"w+(. w+)*(. (? !$))? " Validare: "abc. xyz. +pqr" - eroare în poziția 9 ("+"); „abc. xyz. pqr. "- o 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 enunțurile imbricate ale limbajului 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 o limbă cu ajutorul KA. Prin urmare, este important să puteți converti definițiile limbajului sub formă de expresii regulate într-o definiție sub forma unui FA. O astfel de transformare a fost sugerată de Kennet Thompson.
Mașina de stări este un 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 automatului.
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 de stări este o succesiune de pași. Pasul este determinat de starea automatului și de simbolul de intrare. Pasul în sine constă în schimbarea stării automatului și citirea următorului simbol al secvenței de intrare.
Există următoarele reguli pentru conversia 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. - Automat pentru e-tranziție
2 O expresie regulată dintr-un caracter „a” este convertită într-o mașină cu stări finite din două stări și o tranziție între ele conform semnalului de intrare a (Figura 2).
Figura 2. - Automat pentru sărituri prin simbolul a
3 Să fie o expresie regulată rs și automate finite pentru expresia r, iar expresia s a fost deja construită. Apoi cele două automate sunt conectate în serie. Figura 3 prezintă automatele inițiale pentru limbile r și s. Figura prezintă un automat pentru recunoașterea concatenării acestor limbi.
Automată pentru r Automată pentru s
Figura 3. - Automate inițiale
Figura 4. - Mașină pentru concatenarea limbilor
4 Fie o expresie regulată r | s și automate finite au fost deja construite pentru expresia r și expresia s (Figura 3). Apoi, în automatul rezultat trebuie să existe o alternativă de executare a unuia dintre cele două automate. Adică automatul pentru expresia r | s pentru automate pentru r și s din figura 3 are forma prezentată în figura 5.
Figura 5. - Mașină pentru combinarea limbilor
5 Să existe o expresie regulată r* cu automatul finit construit r. În acest caz, se introduc două stări noi pentru posibilitatea ocolirii automatului expresiei r, și se introduce o e-tranziție între starea finală și starea inițială pentru posibilitatea repetării multiple a automatului r. Dacă un automat similar cu figura 3 este construit pentru expresia regulată r, atunci automatul finit prezentat în figura 6 corespunde expresiei regulate r*.
Setări
Conform teoremei lui Kleene, orice expresie regulată poate fi asociată cu un automat finit, care este un model formal al algoritmului de recunoaștere a lexemelor notate prin această expresie regulată. În termenii cei mai generali, un automat de recunoaștere finit este definit de un set finit de stări ale fluxului de intrare caracteristice acestuia și de tranziții între ele. O schimbare de stare are loc atunci când se primesc caractere ale fluxului de intrare dintr-un alfabet dat în conformitate cu funcția de tranziție , care determină stările ulterioare posibile de la caracterul de intrare și starea curentă. Dintre stările posibile, sunt evidențiate stările inițiale (inițiale) și finale (permiterea), în care mașina de recunoaștere a stării poate fi, respectiv, la începutul și finalizarea procesării jetoanelor fluxului de intrare. Dacă secvența de caractere de intrare poate genera o secvență de tranziții care poate transfera automatul finit din starea inițială în una dintre cele finale, atunci acesta este considerat a fi admisiv și aparține mulțimii obișnuite pe care o recunoaște.
(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 reprezintă caracterele alfabetului de intrare, iar rândurile corespund stărilor curente ale DFA. Elementele fiecărei linii indică stările DFA în care ar trebui să treacă de la starea curentă atunci când primește caracterele corespunzătoare ale alfabetului de intrare. În special, rezultă din prima linie a acestui tabel de tranziție că primirea simbolurilor 0 și 1 în starea inițială Q1 transferă DFA în stările Q4 și, respectiv, Q2.
La recunoașterea secvenței de intrare din tabelul de tranziție, este ușor să urmăriți schimbările de stare ale DFA pentru a determina dacă una dintre stările de acceptare este atinsă sau nu. În special, pentru un vector 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ă cu caracterul alfabetului de intrare care o numește:
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 acceptare Q1, prin urmare, vectorul binar 01001000 aparține mulțimii regulate 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, mai întâi, să descriem algoritmul de construire a unui automat finit determinist din cel original; în al doilea rând, justificați acest algoritm demonstrând riguros că oferă într-adevăr un automat finit care este determinist și echivalent cu cel 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 efectivă.
1. Înlăturarea tranzițiilor λ (arce etichetate \lambda ).
Pentru a trece de la mașina de stare originală M=(V,Q,q_0,F,\delta) la automatul finit echivalent M"=(V,Q",q_0,F",\delta") fără tranziții λ, este suficient să efectuați următoarele transformări în graficul original M.
A. Toate stările, cu excepția stării inițiale, care sunt introduse numai prin arce etichetate \lambda , sunt eliminate; aceasta definește mulțimea Q" a automatului finit M" . Este clar că Q"\subseteq Q . În acest caz, presupunem că starea inițială rămâne aceeași.
b. Mulțimea de arce ale automatului finit M" și etichetele acestora (deci funcția de tranziție M" ) este definită astfel: pentru oricare două stări p,r\in Q",~ p\to_(a)r este valabilă dacă și numai dacă a\în V și una dintre următoarele este valabilă în graficul M: 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). Dar dacă q\in Q" , atunci, firesc, arcul (q,r) se va păstra în M" iar simbolul a va fi unul dintre simbolurile care aparțin etichetei acestui arc (Fig. 7.12).
Astfel, în M" sunt stocate toate arcele M ale căror etichete sunt diferite de \lambda și care leagă o pereche (vârfurile) de stări din mulțimea Q" (neînlăturată conform punctului a). În plus, pentru orice triplu de stări p,q,r (nu neapărat distinct!), 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ă cu \lambda (adică, calea prin tranziții λ), iar de la q la r conduce un arc, a cărui etichetă conține simbolul a al alfabetului de intrare, în M" se construiește un arc de la p la r, a cărui etichetă conține simbolul a (vezi Fig. 7.11).
în. Mulțimea stărilor finale F" ale automatului finit M" conține toate stările q\in Q" , adică stările automatului finit M care nu sunt șterse conform punctului a, pentru care q\Rightarrow_(\lambda)^(\ast)q_f pentru unele q_f\in F (adică fie starea q în sine este starea finală a automatului finit M , fie de la aceasta există o cale de lungime diferită de zero de-a lungul arcurilor etichetate \lambda către una dintre stările finale ale finitului automatul M ) (Fig. 7.13).
2. De fapt determinare.
Lăsa M=(Q,V,q_0,F,\delta) este un automat finit fără tranziții λ. Să construim un automat finit determinist echivalent M_1 .
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 subset al setului de stări ale automatului finit M . În acest caz, starea inițială a noului automat finit (adică M_1 ) este o submulțime singleton care conține starea inițială a vechiului automat finit (adică M ), iar stările finale ale noului automat finit sunt toate astfel de submulțimi Q care conțin cel puțin o finală vârful 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 noului 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, mulțimea Q_1 ar trebui definită ca o mulțime care se află într-o corespondență unu-la-unu cu mulțimea 2^Q , dar este totuși mai convenabil pentru noi să considerăm că Q_1 coincide cu 2^Q , deoarece mulțimea 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 să treacă la setul de stări, care este unirea tuturor mulțimilor de stări ale vechiului automat finit, la pe care acest vechi automat finit îl trece prin 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 mașina de stări 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 caracter 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 de stări deterministe M_1 este absorbantă. De asemenea, este util să rețineți că \delta_1(S,a)=\varnothing dacă și numai dacă pentru fiecare q\in S (stări ale vechiului automat finit din mulțimea stărilor S ) \delta(q,a)=\varnothing, adică în graficul M, fiecare astfel de stare q nu lasă niciun arc marcat cu simbolul a .
Se poate dovedi că automatul finit obținut printr-un astfel de algoritm este echivalent cu cel original.
Exemplul 7.9. 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 absolut necesar să scrieți toate stările sale 2^3=8, dintre care multe nu pot fi accesibile din starea inițială \(q_0\) . Pentru a obține accesibile din stările \(q_0\), și numai din ele, folosim așa-numita metodă de tragere.
Această metodă poate fi descrisă în cazul general după cum urmează.
În automatul finit original (fără arce goale), definim toate seturile de stări care sunt accesibile de la cea inițială, adică. pentru fiecare caracter 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ările unui nou automat (determinist), accesibil de la vârful inițial de-a lungul unei căi de lungime 2. Repetăm procedura descrisă până când nu apar noi seturi de stări (inclusiv cea goală). Se poate arăta că în acest caz se obțin toate astfel de stări ale 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 mai există seturi de stări noi, procedura de „tragere” se termină aici și obținem graficul prezentat în Fig. 7.16.
Complement de limbaj obișnuit
Una 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 . Apoi complementul limbajului L (ca ansamblu 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, indiferent de șirul x din alfabetul V , există o cale unică pentru acesta în M , începând de la începutul starea în care se citește șirul x. Este clar că șirul x este permis de automatul M , adică x\in L(M) , dacă și numai dacă ultima stare a căii specificate este finală. Aceasta implică faptul 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 permite lanțul x dacă și numai dacă automatul finit original M nu o permite. Prin urmare, transformând fiecare stare finală a lui M într-una nefinală și invers, obținem o automat determinist care permite completarea limbajului L .
Teorema demonstrată ne permite să construim un automat finit care nu permite un anumit set de lanțuri prin următoarea metodă: mai întâi, construim un automat care permite un anumit set de lanțuri, apoi îl determinăm și trecem automatului pentru complement. așa cum este indicat în demonstrația teoremei 7.8.
Exemplul 7.10. A. Să construim un automat finit care permite toate șirurile din alfabet \(0;1\), cu excepția șirului 101.
Mai întâi, 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ăugare (ș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ă am inversat rolurile vârfurilor finale și nefinale în automatul prezentat în Fig. 7.17, am obține un automat care admite limbajul \(\lambda,1,10\) , care nu este - așa cum este ușor de observat - mulțimea tuturor șirurilor, altele decât șirul 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 șirul în sine. Iată, de exemplu, calea care poartă lanțul 1011: s_0,s_1,s_2,s_3,t.
b. Să construim un automat finit care permite toate șirurile din alfabet \(0;1\) cu excepția celor care conțin o apariție a șirului 101. Să considerăm un limbaj L, fiecare șir al căruia conține o apariție a șirului 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.
Direct din expresia regulată în acest caz, este ușor de construit un automat finit care să permită limbajul L (Fig. 7.20).
Apoi, prin metoda „tragerii”, vom efectua determinarea. Rezultatul determinării este prezentat în fig. 7.21.
Pentru o rezolvare completă a problemei, doar Fig. 7.21 schimba rolurile vârfurilor finale și non-finale (Fig. 7.22).
în. Să discutăm ideea de a construi un automat finit care să permită acele și numai acele șiruri din alfabet \(0;1\) care nu încep cu șirul 01 și nu se termină cu șirul 11 (adică șirurile de caractere ale forma 01x și șirurile de caractere de forma y11 nu sunt permise, oricare ar fi fost lanțuri x,y\in\(0;1\) ).
În acest caz, complementul limbajului pentru care doriți să construiți un automat finit este mulțimea tuturor astfel de șiruri de zerouri și cele care încep cu șirul 01 sau se termină cu șirul 11. Un automat care admite acest set de șiruri. este construit ca un automat pentru combinare 01(0+1)^(\ast)+(0+1)^(\ast)11 la fel ca în demonstrarea teoremei lui Kleene (vezi Teorema 7.6).
Proprietatea clasei de limbaje regulate care este închisă sub complement (vezi Teorema 7.8) implică imediat că această clasă este închisă sub intersecție, diferențe teoretice și simetrice.
Corolarul 7.3. Pentru oricare două limbi obișnuite L_1 și L_2, următoarele afirmații sunt adevărate:
1) intersecția L_1\cap L_2 este regulată;
2) diferența L_1\setminus L_2 este regulată;
3) diferență simetrică L_1\vartriangle L_2 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 obișnuite în ceea ce privește operațiile de unire, intersecție și adunare este o algebră booleană, în care unitatea este limbajul 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, automatele finite sunt echivalente dacă limbile pe care le permit sunt aceleași. Prin urmare, pentru a verifica echivalența automatelor M_1 și M_2, este suficient să dovedim 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ă construim un automat care admite această diferență și să verifice dacă limbajul pe care îl admite este gol. În general, problema recunoașterii că un limbaj al mașinii de stări este gol 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 mașina cu stări finite este un grafic direcționat, această problemă poate fi rezolvată, de exemplu, folosind căutarea pe lățime. Limbajul permis de automatul finit 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.
