Limbaje Formale, Automate s¸i Compilatoare
Curs 3
2020-21
Structura cursului
1 Automate finite cu ǫ-tranzit¸ii
2 Automatul determinist minimal
Automate finite cuǫ-tranzit¸ii
Curs 3
1 Automate finite cu ǫ-tranzit¸ii
2 Automatul determinist minimal
Automate finite cuǫ-tranzit¸ii
Automate finite cu ǫ-tranzit¸ii
Definit¸ie 1
Un automat finit cu ǫ-tranzit¸ii este un 5-uplu A = (Q, Σ, δ, q 0 , F ), unde:
Q, Σ, q 0 s¸i F sunt definite ca ˆın cazul automatelor finite deterministe
δ este o funct¸ie , δ : Q × (Σ ∪ {ǫ}) → 2 Q , numit ˘a funct¸ia de tranzit¸ie Observat¸ie:
A este automat nedeterminist, dac ˘a δ(q, ǫ) = ∅, ∀q ∈ Q A este automat determinist, dac ˘a, ˆın plus:
|δ(q, a)| = 1, ∀q ∈ Q, ∀a ∈ Σ
Automate finite cuǫ-tranzit¸ii
Extensia lui δ la cuvinte
Cl (q)-mult¸imea st ˘arilor la care se poate ajunge prin ǫ-tranzit¸ii:
q ∈ Cl (q)
q
′∈ Cl (q) ⇒ δ(q
′, ǫ) ⊆ Cl (q )
Dac ˘a S ⊆ Q, atunci not ˘am:
Cl (S) = [
q∈S
Cl (q)
Extensia lui δ la cuvinte: δ ˆ : Q × Σ ∗ → 2 Q
1
δ(q, ǫ) = ˆ Cl (q), ∀q ∈ Q;
2
δ(q, ˆ ua) = Cl(δ(ˆ δ(q, u), a))), ∀q ∈ Q, ∀u ∈ Σ
∗, ∀a ∈ Σ.
Automate finite cuǫ-tranzit¸ii
Extensia lui δ la cuvinte
δ(q, ˆ a) = Cl (δ(Cl (q), a)), ∀q ∈ Q, ∀a ∈ Σ
ˆIn cazul automatelor cu ǫ - tranzit¸ii vom p ˘astra notat¸ia δ ˆ pentru extensie pentru c ˘a, ˆın general, δ(q, ǫ) ˆ 6= δ(q, ǫ) s¸i
δ(q, ˆ a) 6= δ(q, a), a ∈ Σ.
δ(q, ˆ uv) = ˆ δ(ˆ δ(q, u), v ), ∀q ∈ Q, ∀u, v ∈ Σ ∗
Automate finite cuǫ-tranzit¸ii
Limbajul acceptat
Definit¸ie 2
Limbajul acceptat (recunoscut) de automatul cu ǫ-tranzit¸ii A = (Q, Σ, δ, q 0 , F ) este mult¸imea :
L(A) = {w |w ∈ Σ ∗ , δ(q ˆ 0 , w) ∩ F 6= ∅}.
Un cuv ˆant w este recunoscut de un automat A dac ˘a, dup ˘a citirea
ˆın ˆıntregime a cuv ˆantului w , automatul (pornind din starea init¸ial ˘a
q 0 ) poate s ˘a ajung ˘a ˆıntr-o stare final ˘a.
Automate finite cuǫ-tranzit¸ii
Automatul determinist echivalent
Teorema 1
Pentru orice automat A cu ǫ - tranzit¸ii exist ˘a un automat A ′ determinist echivalent cu A
Dac ˘a A = (Q, Σ, δ, q 0 , F ) atunci A ′ = (Q ′ , Σ, δ ′ , q 0 ′ , F ′ ) unde:
Q ′ = 2 Q q 0 ′ = Cl (q 0 ) δ ′ (S, a) = Cl ( S
s∈S δ(s, a)) S ∈ Q ′ , a ∈ Σ
S ∈ F ′ ⇔ S ∩ F 6= ∅
Automate finite cuǫ-tranzit¸ii
Automatul determinist echivalent
Teorema 1
Pentru orice automat A cu ǫ - tranzit¸ii exist ˘a un automat A ′ determinist echivalent cu A
Dac ˘a A = (Q, Σ, δ, q 0 , F ) atunci A ′ = (Q ′ , Σ, δ ′ , q 0 ′ , F ′ ) unde:
Q ′ = 2 Q q 0 ′ = Cl (q 0 ) δ ′ (S, a) = Cl ( S
s∈S δ(s, a)) S ∈ Q ′ , a ∈ Σ S ∈ F ′ ⇔ S ∩ F 6= ∅
Au loc:
δ ′ (q ′ 0 , w ) = ˆ δ(q 0 , w), ∀w ∈ Σ ∗
L(A ′ ) = L(A)
Automate finite cuǫ-tranzit¸ii
Automatul determinist echivalent - algoritm
Intrare: Automatul A (cu ǫ - tranzit¸ii) ; Cl (S)
Ies¸ire: Automatul determinist A
′= (Q
′, Σ, δ
′, q
0′, F
′), echivalent cu A.
q
0′= Cl({q
0}); Q
′= {q
0′} ; marcat(q
′0) = false; F
′= ∅ ; if (q
0′∩ F 6= ∅) then F
′= F
′∪ {q
′0} ; while (∃S ∈ Q
′&&!marcat(S)) {
for (a ∈ Σ){
S
′= Cl ( S
s∈S
δ(s, a));
δ
′(S, a) = S
′; if (S
′6∈ Q
′){
Q
′= Q
′∪ {S
′};
marcat(S
′) = false;
if (S
′∩ F 6= ∅) then F
′= F
′∪ {S
′} ; }
}
marcat(S) = true;
}
Automate finite cuǫ-tranzit¸ii
Exemplu
Automate finite cuǫ-tranzit¸ii
Exemplu
Automatul determinist minimal
Curs 3
1 Automate finite cu ǫ-tranzit¸ii
2 Automatul determinist minimal
Automatul determinist minimal
St ˘ari accesibile
Fie A = (Q, Σ, δ, q 0 , F ) automat finit determinist
Starea q este accesibil ˘a ˆın A dac ˘a exist ˘a un cuv ˆant w ∈ Σ ∗ astfel ˆınc ˆat
q = δ(q 0 , w ).
Automatul determinist minimal
St ˘ari inseparabile
Fie A = (Q, Σ, δ, q 0 , F ) un automat finit determinist.
Definit¸ie 3
St ˘arile q 1 s¸i q 2 sunt inseparabile ˆın raport cu F , (notat q 1 ρq 2 ) ddac ˘a
∀w ∈ Σ ∗ : δ(q 1 , w ) ∈ F ⇔ δ(q 2 , w ) ∈ F
Automatul determinist minimal
St ˘ari inseparabile
Fie A = (Q, Σ, δ, q 0 , F ) un automat finit determinist.
Definit¸ie 3
St ˘arile q 1 s¸i q 2 sunt inseparabile ˆın raport cu F , (notat q 1 ρq 2 ) ddac ˘a
∀w ∈ Σ ∗ : δ(q 1 , w ) ∈ F ⇔ δ(q 2 , w ) ∈ F
Dac ˘a exist ˘a w ∈ Σ ∗ cu δ(q 1 , w ) ∈ F s¸i δ(q 2 , w ) 6∈ F (sau invers),
st ˘arile q 1 s¸i q 2 sunt separabile (de c ˘atre w ), s¸i not ˘am q 1 sep q 2
q 1 sep q2 ⇔ ¬q 1 ρq 2 .
Automatul determinist minimal
St ˘ari inseparabile
Fie A = (Q, Σ, δ, q 0 , F ) un automat finit determinist.
Definit¸ie 3
St ˘arile q 1 s¸i q 2 sunt inseparabile ˆın raport cu F , (notat q 1 ρq 2 ) ddac ˘a
∀w ∈ Σ ∗ : δ(q 1 , w ) ∈ F ⇔ δ(q 2 , w ) ∈ F
Dac ˘a exist ˘a w ∈ Σ ∗ cu δ(q 1 , w ) ∈ F s¸i δ(q 2 , w ) 6∈ F (sau invers), st ˘arile q 1 s¸i q 2 sunt separabile (de c ˘atre w ), s¸i not ˘am q 1 sep q 2 q 1 sep q2 ⇔ ¬q 1 ρq 2 .
Observat¸ie: dac ˘a q 1 ∈ F s¸i q 2 6∈ F , atunci q 1 sep q 2
Automatul determinist minimal
Exemplu
Automatul determinist minimal
Automat minimal
Observat¸ii:
Relatia ρ este relat¸ie de echivalent¸˘a.
∃a ∈ Σ : δ(p, a) sep δ(q, a) = ⇒ p sep q.
Automatul determinist minimal
Automat minimal
Observat¸ii:
Relatia ρ este relat¸ie de echivalent¸˘a.
∃a ∈ Σ : δ(p, a) sep δ(q, a) = ⇒ p sep q.
Teorema 2
Fie A un automat determinist cu toate st ˘arile accesibile. Daca toate
st ˘arile din A sunt separabile ˆın raport cu F, atunci nu exist ˘a un alt
automat A ′ cu num ˘ar mai mic de st ˘ari s¸i L(A) = L(A ′ ).
Automatul determinist minimal
Automatul minimal
Fie A = (Q, Σ, δ, q 0 , F ) un automat finit determinist si relat¸ia ρ.
Dac ˘a ∀ q 1 , q 2 ∈ Q : q 1 sep q 2 , atunci A este minimal.
Altfel, automatul minimal:
A ρ = (Q/ρ, Σ, δ ρ , [q 0 ], F /ρ)
Q/ρ - clasele de echivalent¸˘a ale relat¸iei ρ:
Q/ρ = {[q]|q ∈ Q}
δ
ρ([q], a) = [δ(q, a)]
[q
0] clasa de echivalent¸˘a ˆın care se afl ˘a starea q
0F /ρ = {[q]|q ∈ F }
Automatul determinist minimal
Exemplu
Automatul determinist minimal
Automatul minimal
Fie automatul minimal: A ρ = (Q/ρ, Σ, δ ρ , [q 0 ], F /ρ) Q/ρ - clasele de echivalent¸˘a ale relat¸iei ρ:
δ ρ ([q], a) = [δ(q, a)]
[q 0 ] clasa de echivalent¸˘a ˆın care se afl ˘a starea q 0 F /ρ = {[q]|q ∈ F }
Teorema 3
Fie automatul determinist A, cu toate st ˘arile accesibile. Automatul A ρ
construit ca mai sus este automatul cu num ˘ar minim de st ˘ari care
accept ˘a limbajul L(A).
Automatul determinist minimal
Algoritm pentru determinarea relat¸iei ρ
Fie A = (Q, Σ, δ, q 0 , F ), Q = {q 0 , q 1 , . . . , q n } Tablou separabil [q i , q j ]:
separabil [q
i, q
j] = 1 ddac ˘a q
isep q
j(separabil [q
i, q
j] = 0 ddac ˘a q
iρq
j)
init¸ial separabil[q
i, q
j] = 1 ddac ˘a q
i∈ F , q
j6∈ F (sau invers)
Se va completa apoi separabil[q
i, q
j], pentru 0 ≤ i < j ≤ n, utiliz ˆand
doar valorile calculate anterior in separabil s¸i funct¸ia δ.
Automatul determinist minimal
Algoritm pentru determinarea relat¸iei ρ
lista[p, r ] : (p 6= r )
definit ˘a pentru perechi de st ˘ari cu separabil[p, r] = 0
lista[p, r ] = {(q
i, q
j)|separabil [q
i, q
j] = 0 ∧ exista a ∈ Σ : p = δ(q
i, a), r = δ(q
j, a), (q
i, q
j) 6= (p, r )}
lista se completeaz ˘a pe m ˘asur ˘a ce se completeaz ˘a separabil
Automatul determinist minimal
Algoritm pentru determinarea relat¸iei ρ
Se init¸ializeaz ˘a tabloul separabil (separabil[q i , q j ] = 1, dac ˘a q i ∈ F , q j 6∈ F sau invers)
Pentru orice q i , q j (0 ≤ i < j ≤ n) cu separabil[q i , q j ] = 0 :
Automatul determinist minimal
Algoritm pentru determinarea relat¸iei ρ
Se init¸ializeaz ˘a tabloul separabil (separabil[q i , q j ] = 1, dac ˘a q i ∈ F , q j 6∈ F sau invers)
Pentru orice q i , q j (0 ≤ i < j ≤ n) cu separabil[q i , q j ] = 0 : Dac ˘a exist ˘a a ∈ Σ cu separabil [δ(q
i, a), δ(q
j, a)] = 1, atunci:
separabil[q
i, q
j] = 1
trebuie modificat tabloul separabil pentru toate perechile de st ˘ari a
c ˘aror separabilitate depinde de q
i, q
j(perechile de st ˘ari din
lista[q
i, q
j])
Automatul determinist minimal
Algoritm pentru determinarea relat¸iei ρ
Se init¸ializeaz ˘a tabloul separabil (separabil[q i , q j ] = 1, dac ˘a q i ∈ F , q j 6∈ F sau invers)
Pentru orice q i , q j (0 ≤ i < j ≤ n) cu separabil[q i , q j ] = 0 : Dac ˘a exist ˘a a ∈ Σ cu separabil [δ(q
i, a), δ(q
j, a)] = 1, atunci:
separabil[q
i, q
j] = 1
trebuie modificat tabloul separabil pentru toate perechile de st ˘ari a c ˘aror separabilitate depinde de q
i, q
j(perechile de st ˘ari din lista[q
i, q
j])
Altfel (pentru orice a ∈ Σ are loc separabil [δ(q
i, a), δ(q
j, a)] = 0):
pentru orice a ∈ Σ cu δ(q
i, a) 6= δ(q
j, a) adaug ˘a (q
i, q
j) la
lista[δ(q
i, a), δ(q
j, a)]
Automatul determinist minimal
Algoritm pentru determinarea relat¸iei ρ
//initializarea tablourilor,
se marcheaz˘ a perechile F × (Q − F ) si (Q − F ) × F 1.for (i=0; i<=n-1; i++)
2. for (j=i+1,j<=n; j++) { 3. lista[qi,qj]=∅;
4. if ((qi ∈ F && qj 6∈ F ) || (qi 6∈ F && qj ∈ F ))
5. separabil[qi,qj]=1;
6. else
7. separabil[qi,qj]=0;
8. }
Automatul determinist minimal
9.for (i=0; i<=n-1; i++) 10. for (j=i+1,j<=n; j++) {
//se selecteaza doar starile inseparabile 11. if (separabil[qi,qj]==0) {
//daca exista a astfel incat δ(qi , a) sep δ(qj , a) //inseamna ca qi si qj sunt separabile 12. if ( ∃ a ∈ Σ : separabil [δ(qi, a), δ(qj, a)] == 1) {
// qi si qj devin separabile si la fel toate // perechile de stari dependente de qi,qj
13. update separabil(qi, qj );
14. }
15. else {
16. for (a ∈ Σ : δ(qi , a) 6= δ(qj , a)&& (qi , qj ) 6= (δ(qi , a), δ(qj, a))) 17. adauga (qi, qj) la lista[δ(qi, a), δ(qj, a)]
18. }
19. }
20. }
Automatul determinist minimal
Algoritm pentru determinarea relat¸iei ρ
// qi si qj devin separabile si la fel toate // perechile de stari dependente de qi,qj update separabil(qi, qj ){
separabil[qi , qj ] = 1;
for ((q
i′, q
j′) ∈ lista[qi , qj ]){
if (separabil [q
′i, q
j′] == 0) update separabil(q
′i, q
j′);
}
}
Automatul determinist minimal
Exemplu
Automatul determinist minimal
Exemplu
Automatul determinist minimal
Exemplu
Automatul determinist minimal
Exemplu
Automatul determinist minimal
Exemplu
Automatul determinist minimal
