Necesar de o mașină de stări nedeterministă M = (Q, T, D, q 0 , F) construi o mașină deterministă cu stări finite M = (Q", T, D", q" 0 , F"). Starea inițială pentru automatul în construcție este ε-închiderea stării inițiale a automatului inițial. ε-closure - un set de stări care sunt accesibile de la una dată prin tranziții de-a lungul ε. Mai mult, deși există stări pentru care tranzițiile nu au fost construite (tranzițiile se fac prin simboluri, tranzițiile prin care se află în automatul original), pentru fiecare simbol, ε-închiderea setului de stări care sunt accesibile din starea considerată. prin trecerea prin simbolul considerat se calculează. Dacă starea care corespunde setului găsit există deja, atunci se adaugă o tranziție acolo. Dacă nu, se adaugă noua stare primită.

Exemplu

Inițializare

Sunt marcate stările corespunzătoare închiderii ε a stării inițiale. Aceste stări vor corespunde statului A viitor DKA.

Prima iterație

Există tranziții de la închiderea ε la stările NCA 3 și 10 (conform Ași c, respectiv). Pentru starea 3, ε-închiderea este mulțimea stărilor (3, 4, 6), pentru starea 10 - (10). Să desemnăm noile stări DFA corespunzătoare acestor seturi ca Bși C.

stare DKA	Set de state NFA
		A	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	-	-
C	{10}	-	-	-

A doua iterație

Din setul de stări ale NFA (3, 4, 6) corespunzătoare stării DFA B există două tranziții - la starea 5 (prin b) și 7 (de la c). Închiderile lor ε se intersectează, dar seturile în sine sunt diferite, așa că li se atribuie două stări DFA noi - Dși E. Din statele NFA corespunzătoare stării DFA C, nu există tranziții.

stare DKA	Set de state NFA	Personaje care se pot sări
		A	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	-	-	-
E	{2, 7, 8, 9}	-	-	-

A treia iterație

Din seturile de stări ale NFA corespunzătoare stărilor DFA Dși E se fac tranziții la seturile de stări corespunzătoare stărilor existente (din mulțimea (2, 5, 8, 9) corespunzătoare stării D, pe A trecerea la starea 3 aparținând setului (3, 4, 6) corespunzător stării DFA B, pe c- trecerea la starea 10 corespunzătoare statului C; în mod similar pentru setul corespunzător stării DFA E). Procesul de construire a tabelului stărilor și tranzițiilor DFA este finalizat.

stare DKA	Set de state NFA	Personaje care se pot sări
		A	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	B	-	C
E	{2, 7, 8, 9}	B	-	C

Rezultat:

Construirea unei gramatici liniare drepte dintr-un automat finit

Fiecare stare este asociată cu un non-terminal. Dacă există o tranziție de stat X intr-o stare Y pe A, adăugați regula X → Ay. Pentru stările finale, adăugați reguli X→ e. Pentru ε-tranziții - X → Y.

Exemplul 1 (mașină de stări deterministă)

• A → A b | c C
• B → b D | c E
• C → e
• D → A b | c C
• E → A b | c C

Exemplul 2 (mașină de stări nedeterministă)

• 1 → 2 | 9
• 2 → A 3
• 3 → 4 | 6
• 4 → b 5
• 5 → 8
• 6 → c 7
• 7 → 8
• 8 → 2 | 9
• 9 → c 10
• 10 → ε

Construcția DFA de către RV

Să avem o expresie regulată r. Pe baza acestei expresii regulate, este necesar să se construiască un automat finit determinist D astfel încât L(D) = L(r).

Modificarea expresiei regulate

Să îi adăugăm un simbol, adică sfârșitul RV - „#”. Ca rezultat, obținem o expresie regulată ( r)#.

Construirea unui copac

Să ne imaginăm o expresie regulată ca un arbore, ale cărei frunze sunt caractere terminale, iar nodurile interne sunt operațiile de concatenare „.”, unire „∪” și iterație „*”. Atribuim un număr unic fiecărei frunze a arborelui (cu excepția ε-frunzelor) și ne referim la acesta, pe de o parte, ca poziție în arbore și, pe de altă parte, ca poziție a simbolului corespunzător frunze.

Calculul funcțiilor nullable, firstpos, lastpos

Acum, traversând arborele T de jos în sus de la stânga la dreapta, calculăm trei funcții: nulabil, prima poz, și lastpos. Funcții nulabil, prima pozși lastpos definite la nodurile arborelui. Valoarea tuturor funcțiilor, cu excepția nulabil, este setul de poziții. Funcţie prima poz(n) pentru fiecare nod n al arborelui de sintaxă regex oferă setul de poziții care se potrivesc cu primele caractere din subșirurile generate de subexpresia care se termină la n. De asemenea, lastpos(n) oferă setul de poziții care corespund ultimelor caractere din subșirurile generate de subexpresiile cu vârf n. Pentru noduri n, ale cărui subarbori (adică un arbore al cărui nod n este o rădăcină) poate genera un cuvânt gol, definim noi nulabil(n) = Adevărat, și pentru alte noduri fals. Tabel de calculat nulabil, prima poz, lastpos:

nodul n	nulabil(n)	prima poz(n)	lastpos(n)
ε	Adevărat	∅	∅
i ≠ ε	fals	{i}	{i}
u ∪ v	nulabil(u) sau nulabil(v)	prima poz(u) ∪ prima poz(v)	lastpos(u) ∪ lastpos(v)
tu . v	nulabil(u) și nulabil(v)	dacă nulabil(u) apoi prima poz(u) ∪ prima poz(v) altfel prima poz(u)	dacă nulabil(v) apoi lastpos(u) ∪ lastpos(v) altfel lastpos(v)
v*	Adevărat	prima poz(v)	lastpos(v)

Urmărirea construirii

Funcţie followpos calculat prin nulabil, prima pozși lastpos. Funcţie followpos definite pe mai multe poziții. Sens followpos este un set de poziții. În cazul în care un i- poziţia, atunci followpos(i) sunt multe posturi j astfel încât există niște șir... CD... incluse în limbajul descris de RW, astfel încât i se potrivește cu această intrare c, A j- intrare d. Funcţie followpos poate fi calculat și într-o singură parcurgere a arborelui conform următoarelor două reguli

1. Lasa n- nodul intern cu "." (concatenare); A, b- urmașii săi. Apoi pentru fiecare poziție i inclus în lastpos(A followpos(i) o multime de prima poz(b).
2. Lasa n- nod intern cu operația „*” (iterație), A- descendentul lui. Apoi pentru fiecare poziție i inclus în lastpos(A), se adaugă la setul de valori followpos(i) o multime de prima poz(A).

Exemplu

Calculați valoarea funcției followpos pentru expresia regulată ( A(b|c))*c.

Poziţie	Sens followpos
1: (A (b|c))*c	{2, 3}
2: (A(b |c))*c	{1, 4}
3: (A(b|c ))*c	{1, 4}
4: (A(b|c))*c	{5}

Construirea unui DFA

Un DFA este un set de stări și un set de tranziții între ele. Starea DFA este un set de poziții. Construirea unui DFA constă în adăugarea treptată a stărilor necesare la acesta și construirea de tranziții pentru acestea. Inițial, există o singură stare prima poz(rădăcină) (rădăcină- rădăcina arborelui), care nu are tranziții. Tranziția este efectuată de caractere din expresia regulată. Fiecare caracter corespunde unui set de poziții ( p i). Unirea tuturor followpos(x) este starea în care este necesar să se ajungă, unde x este o poziție care este prezentă atât între pozițiile statului, cât și între pozițiile simbolului din RE, pe care se face trecerea. Dacă nu există o astfel de stare, atunci trebuie adăugată. Procesul trebuie repetat până când sunt construite toate tranzițiile pentru toate stările. Toate statele care conțin poziția simbolului # adăugată la sfârșitul RE sunt declarate definitive.

DFA obținut de la RV ( A(b|c))*c

Exemplu

Creați DFA prin expresie regulată ( A(b|c))*c.

stare DKA	Simbol
	a(1)	b(2)	c(3, 4)
A(1, 4)	B(2, 3)	-	C(5)
B(2, 3)	-	A(1, 4)	A(1, 4)
C(5)	-	-	-

Construirea unui DFA cu un număr minim de state

Un DFA cu un număr minim de state este construit pentru un DFA definit oriunde, de ex. astfel încât . Pentru orice DFA, există un echivalent DFA definit peste tot.

Construirea unui DFA definit peste tot

Introduceți un nou stat și definiți un nou set de state .

Să definim o nouă funcție de tranziție ca aceasta:

Construirea unei partiții (formal)

Să construim partiția inițială P seturi de stări în două grupe: stări finale F si altii S/F, adică P = {F, Q\F}.

Aplicați pentru fiecare grup G ∈ P următoarea procedură. lovitura Gîn subgrupe astfel încât statele sși t din G a ajuns în același grup dacă și numai dacă pentru fiecare simbol de intrare A state sși t au tranziții A statelor din acelaşi grup în P.

Subgrupurile rezultate sunt adăugate la noua partiție P nou.

Accept P = P nou și repetați construcția partiției până la stabilizare, adică până când partiția nu se mai schimbă.

Construirea unei partiții (algoritm)

Pentru a construi o partiție, există următorul algoritm. Construim o tabelă de tranziție pentru automatul original, construim o partiție inițială.

Atribuim un identificator fiecărui grup din partiție (pentru partiția inițială, de exemplu, 0 și 1).

Fiecărei stări (fiecărui rând al tabelului) i se atribuie un șir de forma „a.bcd…xyz”, unde este identificatorul grupului din care aparține starea [prima coloană (de unde mergem), a doua. coloană (unde trecem după primul caracter), …, ultima coloană (unde trecem după ultimul caracter)].

Construim noi grupuri în funcție de coincidența șirurilor, adică astfel încât stările cu aceleași șiruri alocate să se încadreze într-un singur grup.

Apoi, o nouă iterație. Atribuim noi identificatori grupurilor rezultate, de exemplu (0, 1, ..., n). Și repetăm ​​construcția partiției până la stabilizare.

Rețineți că, atunci când mai rămâne o singură stare în grup, în etapele ulterioare ale construcției partiției, nu mai puteți scrie șirul de identificatori pentru această stare, deoarece acest șir va fi unic în orice caz datorită primului caracter al șirul. Cu alte cuvinte, la împărțire, nu se va întâmpla nimic unui grup dintr-o stare - este transferat într-o nouă divizare așa cum este.

Construcția automatului redus

Fiecare dintre grupurile rezultate devine starea unui nou DFA. Dacă grupul conține starea inițială (finală) a automatului original, acest grup devine starea inițială (respectiv finală) a noului DFA. Tranzițiile sunt construite într-un mod evident: o tranziție la o stare de la un grup este considerată o tranziție la un grup.

Aducem aparatul. Îndepărtăm mai întâi cele negeneratoare (sterile, „mort”), apoi stări inaccesibile (definițiile sunt date pentru simboluri, dar într-un mod evident sunt transferate la stările automatului).

În general, eliminarea stărilor moarte transformă un DFA într-un NFA, deoarece într-un DFA trebuie definite toate tranzițiile. Cu toate acestea, în Cartea Dragonului, o astfel de abatere de la definiția formală este încă considerată acceptabilă.

Exemplu

Pentru a construi un DFA cu un număr minim de stări pentru un DFA de următoarea formă:

• Împărțire inițială: (C) ( stare finală), (A, B, D, E) ( toate celelalte state).
• (C)( fara modificari), (A, D, E), (B), ( deoarece trecem de la A, D, E de-a lungul a, c la B și, respectiv, C).
• Nu mai putem face împărțiri.

Fie grupului (C) să corespundă stării C, grupului (A, D, E) stării A și grupului (B) stării B. Apoi obținem un DFA cu un număr minim de stări:

Exemplu (algoritm pentru construirea unei partiții)

Un tabel de tranziție pentru un DFA definit oriunde (starea Z adăugată) corespunzător RV (ab|ε)a*|abb|b*a. Din întrebările de examen din 2012.

	A	b	eu 0	eu 1
→A*	B	C	0.01	0.12
B*	D	E	0.00	1.01
C	F	C	1.01
D*	D	Z	0.01	0.04
E*	D	Z	0.00	1.03
F*	Z	Z	0.11
Z	Z	Z	1.11

Iterații:

• I 0: ABCDEF(0), CZ(1).
• I 1: AD(0), BE(1), C(2), F(3), Z(4).
• I 2: A, B, C, D, E, F, Z.

Rezultat: mașina avea deja numărul minim de stări :-)

DFA care permite completarea limbii

Algoritmul pentru construirea unui DFA care acceptă complementul limbajului L (L̅) constă din doi pași:

• Construirea unui DFA complet
• Construcția automatului dorit din acesta

De fapt, nu există un DFA complet. Sub DKA complet niste profesorii înțeleg automatul, în tabelul de tranziție al căruia nu există celule goale. Cu toate acestea, conform definiției DFA - δ: Q × Σ → Q - nu pot exista celule goale în niciun caz. Automatul „cu celule goale”, însă, satisface definiția NFA. În cursul rezolvării, nu este neobișnuit să obțineți doar un astfel de NFA, căruia îi lipsesc doar tranzițiile înainte de DFA.

Pentru a-l reumple, este suficient să adăugați o nouă stare X, iar tranzițiile inexistente „în loc de” adaugă tranziții la această nouă stare. Nu uitați să adăugați tranziții de la Xîn X. Este ușor de observat că acolo unde automatul original nu a acceptat un lanț din cauza absenței unei tranziții, noul automat va intra în stare Xși agățați-vă de asta. Deoarece noua stare nu este o stare de acceptare (finală), noul automat nu va accepta nici acest lanț.

Acum, pentru a construi automatul dorit, este nevoie doar de schimbarea rolurilor stărilor de acceptare și de neacceptare. Cu alte cuvinte, F" = Q \ F.

Construirea unui analizor LL(k).

Transformarea gramaticală

Nu orice gramatică este analizabilă LL(k). O gramatică fără context aparține clasei LL(1) dacă nu are conflicte FIRST-FIRST (recursiunea stângă este un caz special al unui astfel de conflict) și FIRST-FOLLOW.

Uneori este posibil să se transforme gramaticile non-LL(1) astfel încât acestea să devină LL(1). Unele (mai precis, cele care au fost luate în considerare în curs) sunt prezentate mai jos.

Se elimină recursiunea stângă

Să presupunem că avem o regulă de formă (în continuare, în această secțiune, majuscule - simboluri non-terminale, minuscule - lanțuri de orice caractere):

• A→A A| A b| … | A k | m | n | … | z

Nu este supus unei analize clare, așa că ar trebui convertit.

Este ușor de demonstrat că această regulă este echivalentă cu următoarea pereche de reguli:

• A → m b | n b | … | z B
• B → A b | b b | … | k b | ε

Factorizarea stângă

Esența acestei proceduri este eliminarea ambiguității în alegerea regulilor pentru personajul stâng. Pentru a face acest lucru, se găsește un prefix comun stâng și ceea ce poate urma este scos într-o nouă regulă (litere mici - lanțuri de orice caractere)

Exemplu

• A → A c | A df | A dg | b

Convertit la

• A → A b | b
• B → c | d f | d g

care la rândul său devine

• A → A b | b
• B → c | d Cu
• C → f | g

Exemplu de conversie gramaticală

G= ((S, A, B), (a, b, c), P, S)

• S→SAbB | A
• A→ab | aa | ε
• B → c | ε

Eliminarea recursiunii stângi pentru S:

• S → aS 1
• S1 → AbBS 1 | ε

Factorizarea stângă pentru A:

• A → aA 1 | ε
• A 1 → b | A

Gramatica finala:

• S → aS 1
• S1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | A
• B → c | ε

Clădirea FIRST și FOLLOW

FIRST(α), unde α ∈ (N ∪ T)* este mulțimea de terminale de la care poate începe α. Dacă α ⇒ ε, atunci ε ∈ FIRST(α). În consecință, valoarea FOLLOW( A) pentru non-terminal A- multe terminale care pot apărea imediat după Aîntr-o formă sentimentală. În cazul în care un A poate fi caracterul din dreapta într-o formă de propoziție, atunci jetonul $ final aparține și lui FOLLOW( A)

PRIMUL calcul

Pentru terminale

• Pentru orice terminal X, X ∈ T, PRIMUL( X) = {X}

Pentru non-terminale

• În cazul în care un X este un non-terminal, atunci punem FIRST( X) = {∅}
• Dacă gramatica are o regulă X→ ε, apoi adăugați ε la FIRST( X)
• Pentru fiecare non-terminal Xși pentru fiecare regulă de inferență X → Y 1 …Y k adaugă la FIRST( X) PRIMUL set de toate simbolurile din partea dreaptă a regulii până la primul din care ε nu este derivat, inclusiv

Pentru lanturi

• Pentru șirul de caractere X 1 …X k FIRST este uniunea FIRST caractere incluse în șir până la primul, care are ε ∉ FIRST, inclusiv acesta.

Exemplu

• S → aS 1
• S1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | A
• B → c | ε

PRIMILE non-terminale în ordinea de rezolvare a dependenței:

• FIRST(E) = (a)
• FIRST(A) = (a, ε)
• PRIMUL(A 1) = (b, a)
• FIRST(B) = (c, ε)
• PRIMUL(S 1) = (a, b, ε)

FIRST pentru regulile de inferență:

• FIRST(aS 1) = (a)
• FIRST(AbBS 1) = (a, b)
• FIRST(ε) = (ε)
• FIRST(aA 1) = (a)
• FIRST(a) = (a)
• FIRST(b) = (b)
• FIRST(c) = (c)

Urmăriți calculul

Calcularea funcției FOLLOW pentru caracterul X:

• Fie FOLLOW(X) = (∅)
• Dacă X este o axiomă gramaticală, atunci adăugați markerul $ la FOLLOW
• Pentru toate regulile de forma A → αXβ adăugați FIRST(β)\(ε) la FOLLOW(X) (X poate fi urmat de acele caractere care încep cu β)
• Pentru toate regulile de forma A → αX și A → αXβ, ε ∈ FIRST(β), adăugați FOLLOW(A) la FOLLOW(X) (adică X poate fi urmat de toate caracterele care pot urma lui A, dacă în regula de inferență, X-ul poate fi în extrema dreaptă)
• Repetați cele două paragrafe anterioare atâta timp cât este posibil să adăugați caractere la set

Exemplu

• S → aS 1
• S1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | A
• B → c | ε

Rezultat:

• FOLLOW(E) = ($)
• FOLLOW(S 1) = ($) (S 1 este caracterul din dreapta din regula S → aS 1)
• FOLLOW(A) = (b) (A în regula S 1 → AbBS 1 este urmată de b)
• FOLLOW(A 1) = (b) (A 1 este caracterul din dreapta din regula A → aA 1 , prin urmare adăugând FOLLOW(A) la FOLLOW(A 1))
• FOLLOW(B) = (a, b, $) (adăugați FIRST(S 1)\(ε) (urmează din regula S 1 → AbBS 1), FOLLOW(S 1) (pentru că există S 1 → ε))

Alcătuirea unui tabel

Masa M pentru o pereche non-terminal-terminal (în celulă M[A, A]) specifică regula după care trebuie redus cuvântul de intrare. Tabelul se completează după cum urmează: pentru fiecare regulă de inferență a unei anumite gramatici A → α (unde α este înțeles ca un lanț în partea dreaptă a regulii), se efectuează următoarele acțiuni:

1. Pentru fiecare terminal A∈ FIRST(α) adaugă o regulă A → α la M[A, A]
2. Dacă ε ∈ FIRST(α), atunci pentru fiecare b∈ FOLLOW( A) adăuga A → α la M[A, b]
3. ε ∈ FIRST(α) și $ ∈ FOLLOW( A), adăuga A → α la M[A, $]
4. Toate celulele goale sunt o eroare în cuvântul introdus

Exemplu

Construiește un tabel pentru gramatică

• S → aS 1
• S1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | A
• B → c | ε

Rezultat:

	A	b	c	$
S	S → aS 1 (Prima regulă, deducerea S → aS 1 , a ∈ FIRST(aS 1))	eroare (A patra regulă)	eroare (A patra regulă)	eroare (A patra regulă)
S1	S1 → AbBS 1 (Prima regulă, ieșire S 1 → AbBS 1 , a ∈ FIRST(AbBS 1))	S1 → AbBS 1 (Prima regulă, ieșire S 1 → AbBS 1 , b ∈ FIRST(AbBS 1))	eroare (A patra regulă)	S 1 → ε (A treia regulă, deducerea S 1 → ε, ε ∈ FIRST(ε), $ ∈ FOLLOW(S 1))
A	A → aA 1 (Prima regulă, ieșire A → aA 1 , a ∈ FIRST(aA 1))	A→ε (A doua regulă, ieșire A 1 → ε, b ∈ FOLLOW(A 1))	eroare (A patra regulă)	eroare (A patra regulă)
A 1	A 1 → a (Prima regulă, ieșire A 1 → a, a ∈ FIRST(a))	A 1 → b (Prima regulă, ieșire A 1 → b, b ∈ FIRST(b))	eroare (A patra regulă)	eroare (A patra regulă)
B	B→e	B→e (A doua regulă, deducerea B → ε, a ∈ FOLLOW(B))	B → c (Prima regulă, ieșire B → c, c ∈ FIRST(c))	B→e (A treia regulă, deducerea B → ε, $ ∈ FOLLOW(B))

Analiza șirurilor

Procesul de analiză a unui șir este destul de simplu. Esența sa este următoarea: la fiecare pas se citește simbolul de sus v c lanțul de intrare.

• În cazul în care un v- caracter terminal
  • În cazul în care un v coincide cu cu, apoi sunt amândoi distruși, are loc o schimbare
  • În cazul în care un v nu se potriveste cu cu, atunci este semnalată o eroare de analiză
• În cazul în care un v- simbol non-terminal, c revine la începutul liniei în loc de v partea dreaptă a regulii, care este luată din celula tabelului, este returnată în stivă M[v, c]

Procesul se termină atunci când atât sfoara, cât și stiva au atins marcatorul de sfârșit (#).

Exemplu

Să analizăm șirul „aabbaabcb”:

grămadă	linia	acțiune
S#	A abbaabcb$	S → aS 1
A S1#	A abbaabcb$	schimb
S1#	A bbaabcb$	S1 → AbBS 1
A bbs 1#	A bbaabcb$	A → aA 1
A A 1 bBS 1 #	A bbaabcb$	schimb
A 1 bbs 1#	b baabcb$	A 1 → b
b bbs 1#	b baabcb$	schimb
b B.S. 1#	b aabcb$	schimb
B S1#	A abcb$	B→e
S1#	A abcb$	S1 → AbBS 1
A bbs 1#	A abcb$	A → aA 1
A bbs 1#	A abcb$	A → aA 1
A A 1 bBS 1 #	A abcb$	schimb
A 1 bbs 1#	A bcb$	A 1 → a
A bbs 1#	A bcb$	schimb
b B.S. 1#	b cb$	schimb
B S1#	c b$	B → c
c S1#	c b$	schimb
S1#	b$	S1 → AbBS 1
A bbs 1#	b$	A→ε
b B.S. 1#	b$	schimb
B S1#	$	B→e
S1#	$	S 1 → ε
#	$	gata

Construirea unui analizor LR(k).

Calcularea k în LR(k)

Nu există un algoritm care să permită, în cazul general, să se calculeze k pentru o gramatică arbitrară. De obicei, merită să încercați să construiți un parser LR(1). Dacă are cel mult o operație per set (Shift, Reduce sau Accept), atunci gramatica este LR(0). Dacă, totuși, apare un conflict și o coliziune la construirea unui parser LR(1), atunci această gramatică nu este LR(1) și merită să încercați să construiți LR(2). Dacă nu reușește să-l construiască, atunci LR(3) și așa mai departe.

Completarea gramaticii

Să adăugăm o nouă regulă S" → S și să facem din S" o axiomă a gramaticii. Această regulă suplimentară este necesară pentru a determina când analizorul se termină și lanțul de intrare este permis. Admiterea are loc dacă și numai dacă se poate efectua convoluția conform regulii S → S”.

Construirea unui sistem canonic de mulțimi de situații admisibile LR(1).

La început, există un set I 0 cu configurația analizorului S" → .S, $. Apoi se aplică operația de închidere acestei configurații până când, ca urmare a aplicării acesteia, nu se adaugă noi configurații. , tranzițiile la seturi noi se construiesc prin deplasarea punctului cu un caracter la dreapta (săriturile sunt făcute de caracterul care a fost după punctul înainte de salt și înainte de acesta după săritură), și acele configurații care au fost obținute din cele existente. in acest fel se adauga acestor seturi.Li se aplica si operatia de inchidere, iar intregul proces se repeta pana nu mai apar seturi noi.

Exemplu

Construiți un sistem canonic de mulțimi de situații admisibile LR(1) pentru gramatica specificată:

• S" → S
• S → ABA
• A → Aa | ε
• B → cBc | d

Decizie:

• Construim o închidere pentru configurația S" → .S, $:
  • S → .ABA,$
• Pentru configurațiile rezultate (S → .ABA, $) construim și o închidere:
  • A → .Aa, c
  • A → .Aa, d
  • A → .,c
  • A → ., d
• Pentru configurațiile rezultate (A → .Aa, c; A → .Aa, d) construim și o închidere:
  • A → .Aa, a
  • A → ., a
• Nu mai pot fi construite configurații în starea I 0 - închiderea este construită

• De la I 0, puteți face tranziții de-a lungul S și A și puteți obține un set de configurații I 1 și I 2, constând din următoarele elemente:
  • I 1 = (S" → S., $)
  • I 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
• I 1 nu necesită închidere
• Să construim închiderea I 2:
  • B → .cBc, a
  • B → .cBc, $
  • B → .d, a
  • B → .d, $
• Toate celelalte seturi sunt construite în mod similar.

Construirea tabelului de analiză

Ultimul pas în construirea unui parser LR(1) este construirea de tabele Acțiuneși mergi la. Masa Acțiune construit pentru caractere șiruri de caractere introduse, adică pentru terminale și marcatorul de sfârșit de linie $, tabel mergi la este construit pentru simboluri gramaticale, adică pentru terminale și non-terminale.

Construirea unui tabel Goto

Tabelul Goto arată în ce stare să mergeți când este întâlnit următorul simbol gramatical. Prin urmare, dacă în sistemul canonic de mulțimi există o trecere de la eu iîn eu j prin simbolul A, apoi în Goto( eu i, A) punem statul eu j. După completarea tabelului, presupunem că în toate celulele goale Goto( eu i, A) = Eroare

Construirea tabelului de acțiuni

• Dacă există o tranziție pe terminalul a de la starea I i la starea I j , atunci Acțiune(I i , a) = Shift(I j)
• Dacă A ≠ S" și există o configurație A → α., a, atunci Acțiune(I i , a) = Reduce(A → α)
• Pentru o stare I i care are o configurație S" → S., $, Action(I i , $) = Accept
• Pentru toate celulele goale Acțiune(I i , a) = Eroare

Exemplu

Construiți tabele de acțiune și Goto pentru gramatică

• S" → S
• S → ABA
• A → Aa | ε
• B → cBc | d

Decizie:

	Acțiune				mergi la
	A	c	d	$	S	S"	A	B	A	c	d
eu 0	Reduce (A → ε)	Reduce (A → ε)	Reduce (A → ε)		eu 1		eu 2
eu 1				Accept
eu 2	Shift (I 6)	Shift (I 4)	Shift (I 5)					eu 3	eu 6	eu 4	eu 5
eu 3	Reduce (A → ε)			Reduce (A → ε)			eu 13
eu 4		Shift (I 8)	Shift (I 9)					eu 7		eu 8	eu 9
eu 5	Reduceți (B → d)			Reduceți (B → d)
eu 6	Reduce (A → Aa)	Reduce (A → Aa)	Reduce (A → Aa)
eu 7		Shift (I 10)								eu 10
eu 8		Shift (I 8)	Shift (I 9)					eu 11		eu 8	eu 9
eu 9		Reduceți (B → d)
eu 10	Reduce (B → cBc)			Reduce (B → cBc)
eu 11		Shift (I 12)								eu 12
eu 12		Reduce (B → cBc)
eu 13	Shift (I 14)			Reduce (S → ABA)					eu 14
eu 14	Reduce (A → Aa)			Reduce (A → Aa)

Analiza lanțului

La fiecare pas, se citește caracterul de sus v din stiva analizorului și luați ultimul caracter c lanțul de intrare.

Dacă în tabelul acțiunilor de la intersecție vși c situat:

• Schimb( eu k), apoi puneți pe stivă cuși apoi eu k. în care c scos din sfoară.
• Reduce( A → u), apoi toate simbolurile terminale și non-terminale care alcătuiesc lanțul sunt șterse din partea de sus a stivei u, dupa care se uita statul Sunt ramanand in varf. Conform tabelului de tranziție de la intersecție Suntși A găsiți următoarea stare Este. Apoi A este împins pe stivă și apoi Este. Linia rămâne neschimbată.
• Acceptați, apoi analizarea este completă
• golul este o greșeală

Exemplu

Să construim analiza șirului aaaccdcc:

Grămadă	Linia	Acțiune
eu 0	A aaccdcc$	Reduceți (A → ε), mergeți la I 2
eu 0 A eu 2	A aaccdcc$	Shift (I 6)
I 0 A I 2 a eu 6	A accdcc$	Reduceți (A → Aa), treceți la I 2
eu 0 A eu 2	A accdcc$	Shift (I 6)
I 0 A I 2 a eu 6	A ccdcc$	Reduceți (A → Aa), treceți la I 2
eu 0 A eu 2	A ccdcc$	Shift (I 6)
I 0 A I 2 a eu 6	c cdcc$	Reduceți (A → Aa), treceți la I 2
eu 0 A eu 2	c cdcc$	Shift (I 4)
I 0 A I 2 s eu 4	c dcc$	Shift (I 8)
I 0 A I 2 c I 4 c eu 8	d cc$	Shift (I 9)
I 0 A I 2 c I 4 c I 8 d eu 9	c c$	Reduceți (B → d), treceți la I 11
I 0 A I 2 c I 4 c I 8 B eu 11	c c$	Shift (I 12)
I 0 A I 2 c I 4 c I 8 B I 11 c eu 12	c$	Reduceți (B → cBc), treceți la I 7
I 0 A I 2 c I 4 B eu 7	c$	Shift (I 10)
I 0 A I 2 c I 4 B I 7 c eu 10	$	Reduceți (B → cBc), treceți la I 3
I 0 A I 2 B eu 3	$	Reduceți (A → ε), treceți la I 13
I 0 A I 2 B I 3 A eu 13	$	Reduceți (S → ABA), treceți la I 1
eu 0 S eu 1	$	Accept

Traducerea expresiilor aritmetice (algoritmul Seti-Ullman)

Notă. Codul este generat de cainele Motorola, de exemplu.

Op Arg1, Arg2

reprezintă

Arg2 = Arg1 Op Arg2

Construirea unui copac

Arborele este construit ca de obicei pentru o expresie aritmetică: La rădăcină, operația cu cea mai mică prioritate, urmată de operații cu o prioritate puțin mai mare și așa mai departe. Parantezele au cea mai mare prioritate. Dacă există mai multe operații cu aceeași prioritate - a op b op c, atunci arborele este construit ca pentru expresia (a op b) op c.

Exemplu

Construiți un arbore pentru expresia a + b / (d + a − b × c / d − e) + c × d

Decizie: Scriem expresia sub forma

((a) + ((b) / ((((d) + (a)) − ((b) × (c)) / (d)) − (e)))) + ((c) × ( d))

Apoi, la rădăcina fiecărui subarboresc va exista o operație, iar expresiile dintre paranteze în stânga și dreapta acestuia vor fi subarborele acestuia. De exemplu, pentru subexpresia ((b) × (c)) / (d), rădăcina subarborelui corespunzător va fi operația „/”, iar subarborele sale vor fi subexpresiile ((b) × (c)) și (d).

Aspect arborescent (calculul numărului de registre)

• Dacă vârful este frunza stângă (adică o variabilă), atunci îl marchem cu zero.
• Dacă vârful este frunza dreaptă, atunci o marchem cu una
• Dacă marcam ambii subarbori pentru un vârf, atunci îl marchem după cum urmează:
  • Dacă subarborele din stânga și din dreapta sunt etichetate cu numere diferite, atunci alegeți cel mai mare dintre ei
  • Dacă subarborele din stânga și din dreapta sunt etichetate cu aceleași numere, atunci acestui subarbore i se atribuie un număr care este cu unul mai mare decât cel care etichetează subarborele

marcajele frunzelor	Aspect arbore cu subarbori identici	Subarborele din stânga este etichetat cu un număr mare	Subarborele din dreapta este etichetat cu un număr mare

dreapta - la fel ca un strămoș.

Dacă eticheta stânga descendent Mai mult etichete dreapta, apoi dreapta copilului i se atribuie registru încă una decât strămoșul și stânga - la fel ca un strămoș.

Codul este format prin parcurgerea arborelui de jos în sus, după cum urmează:

1. Nu este generat niciun cod pentru vârful cu eticheta 0

2. Dacă partea de sus este foaia X cu eticheta 1 și înregistrarea R i, apoi codul

MUȘTĂ X, Ri

3. Dacă vârful este intern cu registrul R i iar copilul său din stânga este foaia X cu eticheta 0, apoi corespunde codului

<Код правого поддерева>OpX, Ri

4. Dacă subarborele unui vârf cu registrul R i- nu frunze și eticheta vârfului din dreapta este mai mare sau egală cu eticheta celui din stânga (care are registrul Rj, j = i + 1), atunci codul corespunde vârfului

<Код dreapta subarbore><Код stânga subarbori > Op Rj, Ri

5. Dacă subarborele vârfului cu registrul R i- nu frunze și eticheta vârfului din dreapta (pentru care registrul Rj, j = i + 1) este mai mică decât eticheta celui din stânga, atunci codul corespunde vârfului

Distribuția registrului este prezentată în graficul din dreapta. Cod generat:

MOVE d, R0 ;R0 = d MOVE c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d MOVE a, R1 ;R1 = a ADD d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) MOVE e, R1 ;R1 = e SUB R0, R1 ;R1 = ((a + d) − ((b × c) / d)) − e MOVE R1, R0;R0 = ((a + d) − ((b × c) / d)) − e DIV b, R0 ;R0 = b / (((a + d) − ((b × c) / d)) − e) ADD a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d )) − e)) MOVE d, R1 ;R1 = d MUL c, R1 ;R1 = c × d ADD R0, R1 ;R1 = (a + (b / (((a + d) − ((b × c) ) / d)) − e))) + (c × d) MUTAȚI R1, R0;R0 = (a + (b / (((a + d) − ((b × c) / d)) − e) )) + (c × d)

Traducerea expresiilor logice

Această secțiune arată cum se generează cod pentru evaluarea leneșă a expresiilor booleene. Ca rezultat al algoritmului, se obține o bucată de cod care, folosind operațiile TST, BNE, BEQ, calculează o expresie logică prin trecerea la una dintre etichetele: TRUELAB sau FALSELAB.

Construirea unui copac

Arborele unei expresii logice reflectă ordinea în care este evaluată în funcție de precedența operațiilor, adică pentru a evalua valoarea unui nod de arbore (care este operația a doi operanzi care sunt subarbori ai nodului), trebuie mai întâi calculați valorile subarborilor săi.

Prioritatea operațiunii: Operatorul NOT are cea mai mare prioritate, urmat de AND și apoi OR. Dacă în expresie sunt folosite alte operații logice, atunci ele trebuie exprimate prin aceste trei într-un anumit mod (de obicei, nu există alte operații și nu este necesară conversia expresiei). Asociativitatea pentru operațiile cu aceeași prioritate este de la stânga la dreapta, adică A și B și C sunt tratate ca (A și B) și C

Exemplu

Construiți un arbore pentru expresia logică nu A sau B și C și (B sau nu C).

Decizie: vezi diagrama din dreapta.

Pentru fiecare vârf al arborelui se calculează 4 atribute:

• Numărul nodului
• Eticheta la care săriți dacă expresia din nod este falsă (etichetă falsă, fl)
• Eticheta la care săriți dacă expresia din nod este adevărată (etichetă adevărată, tl)
• Etichetă-semn (semn) (pentru mai multe detalii, vezi mai jos)

Nodurile sunt numerotate în ordine aleatorie, singura condiție este unicitatea numerelor nodurilor.

Dispunerea arborelui se face după cum urmează:

• fl specifică numărul vârfului la care se face tranziția sau falselab dacă acest vârf este fals
• tl indică numărul vârfului la care se face tranziția sau truelab dacă acest vârf este adevărat

Semnul specifică caz ​​în care evaluarea subarborelui curent poate fi încheiată.

Pentru rădăcina arborelui, fl=falselab, tl=truelab, semn=fals.

Prin urmare:

Exemplu

Marcați arborele construit pentru expresia logică nu A sau B și C și (B sau nu C).

Generarea codului

Comenzile de mașină utilizate în codul generat:

• TST - verificarea argumentului pentru adevăr și stabilirea unui steag dacă argumentul este fals
• BNE - săriți la etichetă dacă steagul nu este setat, adică starea verificată cu TST Adevărat
• BEQ - sari pe eticheta daca steagul este setat, adica starea verificata cu TST fals

Codul este construit după cum urmează:

• arborele este parcurs de la rădăcină, pentru AND și SAU se parcurge mai întâi subarborele din stânga, apoi cel din dreapta
• pentru fiecare vârf trecut, se tipărește numărul (eticheta) acestuia
• pentru foaia A (număr, tl, fl, semn) se imprimă TST A
  • dacă semnul == adevărat, este tipărit BNE tl
  • dacă semnul == fals, BEQ fl este tipărit

Exemplu

Pentru expresia de mai sus se va genera următorul cod:

1:2:4: TST A BEQ TRUELAB 3:5:7: TST B BEQ FALSELAB 8: TST C BEQ FALSELAB 6:9: TST B BNE TRUELAB 10:11: TST C BNE FALSELAB TRUELAB: FALSELAB:

Metoda de potrivire a mostrelor

Ideea metodei este că pentru aceeași secțiune a programului, codul poate fi generat în moduri diferite și, ca urmare, optimizarea poate fi realizată pentru unul sau altul parametru.

Formularea problemei

Există multe mostre, fiecare dintre acestea fiind definită de o bucată din reprezentarea intermediară pentru care este aplicabilă, greutatea și codul generat. Există un arbore de reprezentare intermediar, care este un fragment al programului pentru care este necesar să se genereze cod. Scopul este de a construi o astfel de acoperire a arborelui de reprezentare intermediar cu mostre, astfel încât greutatea totală a probelor să fie minimă.

Modelele sunt instrucțiuni de asamblare și arborii de analiză care le corespund. Pentru fiecare probă se cunoaşte timpul de execuţie al acestuia (în cicluri). Cu ajutorul lor, vom genera codul optim (din punct de vedere al timpului de execuție).

Exemple de exemple

Construirea unei reprezentări intermediare

Mai întâi, construim un arbore de analiză pentru întreaga expresie.

Construirea unei acoperiri

Acum pentru fiecare vârf (le parcurgem în ordine de la frunze la rădăcină), vom genera codul optim pentru subarborele său. Pentru a face acest lucru, trecem pur și simplu prin toate eșantioanele care sunt aplicabile la un punct dat. Timpul de execuție atunci când se folosește un anumit model va fi suma timpului necesar pentru evaluarea argumentelor acestuia (și cunoaștem deja codul optim pentru calcularea lor datorită ordinii de traversare a arborelui) și timpul de execuție a modelului în sine. Dintre toate opțiunile obținute, o alegem pe cea mai bună - va fi codul optim pentru subarborele acestui vârf. La rădăcina arborelui, obținem codul optim pentru întreaga expresie.

Generarea codului

Nu este necesar să scrieți codul pentru toate nodurile - este suficient să notați timpul minim necesar și eșantionul pe care trebuie să îl utilizați. Orice altceva din aceasta este ușor de restaurat.

Avem un număr infinit de registre în aceste probleme, așa că de fiecare dată poți folosi unul nou.

Construcția de RV conform DKA

Construirea NFA după gramatica liniară dreapta

Casting de gramatică

Pentru a converti o gramatică COP arbitrară în forma redusă, trebuie să efectuați următorii pași:

• eliminați toate caracterele sterile;
• eliminați toate caracterele inaccesibile;

Eliminarea caracterelor inutile

Intrare: COP-gramatica G = (T, N, P, S).

Ieșire: O gramatică COP G' = (T, N', P', S) care nu conține simboluri sterile, pentru care L(G) = L(G').

Metodă:

Construiți recursiv mulțimi N 0 , N 1 , ...

1. N 0 = ∅, i = 1.
2. N i = (A | (A → α) ∈ P și α ∈ (N i - 1 ∪ T)*) ∪ N i-1 .
3. Dacă N i ≠ N i - 1, atunci i = i + 1 și treceți la pasul 2, în caz contrar N’ = N i ; P' constă din reguli ale mulţimii P care conţin numai simboluri din N' ∪ T; G' = (T, N', P', S).

Definiție: se spune că un simbol x ∈ (T ∪ N) este inaccesibil într-o gramatică G = (T, N, P, S) dacă nu apare în nicio formă de propoziție a acestei gramatici.

Exemplu

Eliminați caracterele inutile din gramatică G((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)

• S → AcDe | CaDbCe | Saca | aCb | dFg
• A → SeAd | cSA
• B → CaBd | aDBc | BSC | bfg
• C→Ebd | Seb | aAc | cfF
• D→fCE | ac | dEdAS | ε
• E→ESacD | aec | eFF

Decizie

• N 0 = ∅
• N 1 = (B (B → bfg) , D (D → ac) , E (E → aec) )
• N 2 = (B, D, E, C (C → Ebd) )
• N 3 = (B, D, E, C, S (S → aCb) )
• N 4 \u003d (B, D, E, C, S) \u003d N 3

G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | Saca | aCb
• B → CaBd | aDBc | BSC | bfg
• C→Ebd | Seb
• D→fCE | ac | ε
• E→ESacD | aec

Eliminarea caracterelor inaccesibile

Intrare: Gramatica COP G = (T, N, P, S)

Ieșire: O gramatică COP G' = (T', N', P', S) care nu conține simboluri inaccesibile, pentru care L(G) = L(G').

Metodă:

1. V0 = (S); i = 1.
2. V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P și A ∈ V i - 1 ) ∪ V i-1 .
3. Dacă V i ≠ V i - 1 , atunci i = i + 1 și treceți la pasul 2, în caz contrar N’ = V i ∩ N; T' = V i ∩ T; P' constă din regulile mulţimii P conţinând numai simboluri din V i ; G' = (T', N', P', S).

Definiție: Se spune că o gramatică COP G este redusă dacă nu conține simboluri de neatins și steril.

Exemplu

Eliminați caracterele inaccesibile din gramatica G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | Saca | aCb
• B → CaBd | aDBc | BSC | bfg
• C→Ebd | Seb
• D→fCE | ac | ε
• E→ESacD | aec

Decizie

• V 0 = (S)
• V 1 = (S, C (S → CaDbCe) , D (S → CaDbCe) , a (S → CaDbCe) , b (S → CaDbCe) , e (S → CaDbCe) )
• V 2 = (S, C, D, a, b, e, E (C → Ebd) , d (C → Ebd) , f (D → fCE) )
• V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD) )
• V 4 \u003d (S, C, D, E, a, b, d, e, f, c) \u003d V 3

G""((C, D, E, S), (a, b, c, d, e, f), P"", S)

• S → CaDbCe | Saca | aCb
• C→Ebd | Seb
• D→fCE | ac | ε
• E→ESacD | aec

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ă mulțimea 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ă existe o expresie regulată rs și automate finite pentru expresia r și 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 Să 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 automatele pentru r și s din figura 3 are forma prezentată în figura 5.

Figura 5. - Mașină pentru combinarea limbilor

5 Fie o expresie regulată r* cu automatul finit construit r. În acest caz, se introduc două stări noi pentru posibilitatea de ocolire a 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-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 se disting stările inițiale (inițiale) și cele finale (permite), în care automatul-recunoaștere finit poate fi localizat, respectiv, la începutul și finalizarea prelucrării jetoanelor fluxului de intrare. Dacă secvența de introducere a caracterelor poate genera o secvență de tranziții care poate transfera automatul finit din starea inițială în una dintre cele finale, atunci se consideră că este acceptant ș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ă

Expresiile regulate (RE) sunt o formă foarte convenabilă de a scrie așa-numitele limbaje regulate sau automate. Prin urmare, RT este folosit ca limbaj de intrare în multe sisteme care procesează lanțuri. Luați în considerare exemple de astfel de sisteme:

• Comanda grep Unix sau comenzi similare pentru căutarea șirurilor de caractere, așa cum se găsesc în browserele Web sau sistemele de formatare a textului. În astfel de sisteme, RE sunt folosite pentru a descrie modelele pe care utilizatorul le caută într-un fișier. Diverse motoare de căutare convertesc RT fie într-o mașină cu stări finite deterministă (DFA) fie într-o mașină cu stări finite nedeterministă (NFA) și aplică această mașină cu stări fișierului căutat.
• Generatoare de analizoare lexicale. Analizatoarele lexicale sunt o componentă a compilatorului, ele despart programul sursă în unități logice (tokens), care pot consta din unul sau mai multe caractere și au un anumit sens. Generatorul analizor lexical preia descrierile formale ale token-urilor, care sunt în esență RE, și creează un DFA care recunoaște ce simbol apare în intrarea sa.
• RT în limbaje de programare.

În acest articol, ne vom familiariza mai întâi cu automatele finite și tipurile lor (DFA și NFA), apoi vom lua în considerare un exemplu de construire a unui DFA minim folosind o expresie regulată.

Mașini de stat

Un automat finit (FA) este un convertor care vă permite să asociați o intrare cu o ieșire corespunzătoare, iar această ieșire poate depinde nu numai de intrarea curentă, ci și de ceea ce s-a întâmplat înainte, de preistoria automatului finit. Chiar și comportamentul uman, și nu doar sistemele artificiale, poate fi descris folosind CA. Folosind KA, se poate descrie nu numai comportamentul sistemelor artificiale, ci chiar și comportamentul uman. De exemplu, reacția ta la faptul că vecinul tău ascultă muzică tare noaptea va fi una după prima astfel de apariție și complet diferită după mai multe astfel de apariții. Pot exista un număr infinit de astfel de povești de fundal, se pune întrebarea; Ce fel de memorie ar trebui să aibă o navă spațială pentru a se comporta diferit pentru fiecare prearanjare? Este clar că nu se poate stoca un număr infinit de preistorie. Prin urmare, automatul, așa cum spune, împarte toată preistoria posibilă în clase de echivalență. Două istorii sunt echivalente dacă afectează în mod egal comportamentul automatului în viitor. Clasa de echivalență căreia automatul și-a atribuit istoria actuală se mai numește și starea internă a automatului.

Acum să ne uităm la modurile în care poate fi specificat CA. Ele pot fi specificate sub formă de grafice sau sub formă de tabele de control. Sub forma unui grafic, KA este specificat în felul următor:

• vârfurile graficului corespund stărilor CA.
• muchiile direcționate corespund funcțiilor de tranziție (lângă fiecare astfel de muchie este indicat simbolul de-a lungul căruia se realizează tranziția).
• cu starea inițială corespunde un vârf cu o muchie care intră în el care nu iese mai mult de o stare.
• stările finale ale CA sunt marcate cu un contur aldine.

Sub forma unui tabel de control, astfel:

• Stările KA sunt situate în rândurile tabelului.
• caractere ale limbii recunoscute – în coloane.
• la intersectie este indicata starea la care se poate ajunge din starea data prin simbolul dat.

Un exemplu de KA sub forma unui grafic și sub forma unui tabel de control va fi prezentat mai jos.

DKA și NKA

Principala diferență dintre un DFA și un NFA este că DFA poate fi într-o singură stare în timpul funcționării, în timp ce NFA poate fi în mai multe state în același timp. Ca exemplu al lucrării NCA, se poate cita ideea fizicianului american Hugh Everett că orice eveniment sparge lumea în mai multe lumi, în fiecare din care acest eveniment s-a încheiat în felul său. De exemplu, într-o lume, Hitler a câștigat Lumea a 2-a. război, în altul - Newton în loc de fizică a intrat în afaceri și descoperirea legilor mecanicii clasice a trebuit să fie amânată cu 50 de ani. Pentru a trage orice concluzie din funcționarea mașinii, ar trebui să studiem toate „lumile”. După ce a fost citit întregul lanț de intrare, presupunem că NFA acceptă acest lanț dacă și-a încheiat munca într-o stare de acceptare în cel puțin una dintre multele „lumi”. În consecință, automatul respinge treapta dacă a terminat într-o stare inacceptabilă în fiecare „lume”. DFA, pe de altă parte, acceptă un șir, acest lucru este evident dacă, după citirea întregului șir de intrare, se găsește într-o stare de acceptare.

În majoritatea cazurilor, construirea unui NFA este mult mai ușoară decât construirea unui DFA. Dar, în ciuda acestui fapt, utilizarea NFA pentru modelare nu este o idee bună. Din fericire, pentru fiecare NFA este posibil să se construiască un DFA care acceptă același limbaj de introducere. În acest articol, nu vom prezenta un algoritm pentru construirea unui DFA dintr-un NFA, dar luăm în considerare acest algoritm pe baza unui exemplu vizual de mai jos.

Crearea unui DFA minim dintr-o expresie regulată

Pentru început, iată sintaxa RW folosită în acest articol:

• concatenarea este specificată cu un spațiu sau un șir gol (de exemplu: ab)
• unire, folosind simbolul „|”
• iterație (închidere Kleene), cu simbolul „*”.

Luați în considerare un exemplu dat unei expresii regulate:

xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

Este necesar să construiți un DFA minim dintr-o expresie regulată și să demonstrați recunoașterea unui șir corect și incorect.

Pentru început, simplificăm acest RS, folosind legea distributivă dreaptă a concatenării în raport cu uniunea, obținem următorul RS:

(xy* | ab | (x | a*)) (x | y*)

Acum construim un automat pentru acest RV:

Conform regulii de transformare a concatenării (nu vom da regulile pentru transformarea RT în KA, deoarece sunt destul de evidente), obținem următorul automat:

Prin regula de transformare a sindicatului:

Conform regulii de transformare a concatenării:

Și la sfârșit aplicăm regula transformării închiderii și obținem εNCA:

Scăpăm de tranzițiile ε („asteriscul” denotă stări finale):

În acest NFA, stările s3 și s5 sunt echivalente, deoarece δ(s3, x) = δ(s5, x) = s1 și δ(s3, y) = δ(s5, y) = s5, s7. Redenumiți stările s6 -> s5 și s7 -> s6:

Construim DFA conform NFA:

În acest DFA, stările p1 și p5 sunt echivalente, deoarece
δ(p1, x) = δ(p5, x) = p4 și δ(p1, y) = δ(p5, y) = p5. Redenumiți stările p6 -> p5 și p7 -> p6:

Acest automat este DFA minim.

Fie δ funcția de tranziție, apoi funcția de tranziție extinsă construită din δ va fi notată cu δ', iar ω este șirul de intrare.

Fie introdus lanțul ω = aaax, ne așteptăm ca automatul să fie într-una dintre stările de acceptare.

δ'(p0, ε) = p0
δ'(p0, a) = δ(δ'(p0, ε), a) = δ(p0, a) = p3
δ'(p0, aa) = δ(δ'(p0, a), a) = δ(p3, a) = p5
δ'(p0, aaa) = δ(δ'(p0, aa), a) = δ(p5, a) = p5
δ'(p0, aaax) = δ(δ'(p0, aaa), a) = δ(p5, a) = p4

p4 este o stare finală validă, deci șirul aaax este valabil pentru acest automat.

Acum să presupunem că ω = xyyb:

δ'(p0, ε) = p0
δ'(p0, x) = δ(δ'(p0, ε), x) = δ(p0, x) = p1
δ'(p0, xy) = δ(δ'(p0, x), y) = δ(p1, y) = p1
δ'(p0, xyy) = δ(δ'(p0, xy), y) = δ(p1, y) = p1
δ'(p0, xyyb) = δ(δ'(p0, xyy), b) = δ(p1, b) = ∅

Aici vedem că dacă simbolul b este introdus automat în starea p1, atunci acest automat va muri, prin urmare lanțul xyyb este incorect.

P.S. În acest articol, a fost luat în considerare algoritmul pentru construirea unui DFA prin RT, dar există algoritmi mai convenabili, în special pentru programare, dar acesta este un subiect pentru un alt articol ...

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, să justifice acest algoritm prin demonstrarea riguroasă că dă î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: mai întâi, arcele cu eticheta \lambda sunt îndepărtate, apoi se realizează determinarea propriu-zisă.

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, desigur, arcul (q,r) se va păstra în M" și simbolul a va fi unul dintre simbolurile care aparțin etichetei acestui arc (Fig. 7.12).

Astfel, în M" sunt stocate toate arcele lui M ale căror etichete sunt diferite de \lambda și care conectează 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 distincte!), 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 ea o cale de lungime diferită de zero de-a lungul arcurilor etichetate \lambda duce la una dintre stările finale ale automatului finit M ) (Fig. 7.13).

2. De fapt determinare.

Lasa 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 trece în mulțimea 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 demonstra 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 unui traseu de lungime 2. Repetăm ​​procedura descrisă până când nu apar noi setări 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 face.

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 alfabetul \(0;1\) , cu excepția celor care conțin o apariție a șirului 101. Să considerăm un limbaj L , fiecare șir din care conține o apariție a șirului 101. Poate fi definit astfel:

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 forma y11 nu sunt permise, oricare ar fi 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 șiruri de zerouri și cele care încep cu șirul 01 sau se termină cu șirul 11. Un automat care admite acest set de strings 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 fiind î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 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, automatele finite sunt echivalente dacă limbajele 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 faptului 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.