Post on 31-Dec-2019
Limbaje Formale, Automate si Compilatoare
Curs 3
2019-20
LFAC (2019-20) Curs 3 1 / 25
Structura cursului
1 Automate finite cu ǫ-tranzitii
2 Automatul determinist minimal
LFAC (2019-20) Curs 3 2 / 25
Automate finite cu ǫ-tranzitii
Curs 3
1 Automate finite cu ǫ-tranzitii
2 Automatul determinist minimal
LFAC (2019-20) Curs 3 3 / 25
Automate finite cu ǫ-tranzitii
Automate finite cu ǫ-tranzitii
Definitie 1
Un automat finit cu ǫ-tranzitii este un 5-uplu A = (Q,Σ, δ, q0,F ), unde:
Q, Σ, q0 si F sunt definite ca ın cazul automatelor finite
deterministe
δ este o functie , δ : Q × (Σ∪{ǫ}) → 2Q, numita functia de tranzitie
Observatie:
A este automat nedeterminist, daca δ(q, ǫ) = ∅, ∀q ∈ Q
A este automat determinist, daca, ın plus:
|δ(q, a)| = 1, ∀q ∈ Q, ∀a ∈ Σ
LFAC (2019-20) Curs 3 4 / 25
Automate finite cu ǫ-tranzitii
Extensia lui δ la cuvinte
Cl(q)-multimea starilor la care se poate ajunge prin ǫ-tranzitii:
q ∈ Cl(q)
q′ ∈ Cl(q) ⇒ δ(q′, ǫ) ⊆ Cl(q)
Daca S ⊆ Q, atunci notam:
Cl(S) =⋃
q∈S
Cl(q)
Extensia lui δ la cuvinte: δ : Q × Σ∗ → 2Q
1 δ(q, ǫ) = Cl(q), ∀q ∈ Q;2 δ(q,ua) = Cl(δ(δ(q,u),a))), ∀q ∈ Q, ∀u ∈ Σ∗, ∀a ∈ Σ.
LFAC (2019-20) Curs 3 5 / 25
Automate finite cu ǫ-tranzitii
Extensia lui δ la cuvinte
δ(q, a) = Cl(δ(Cl(q), a)), ∀q ∈ Q, ∀a ∈ Σ
In cazul automatelor cu ǫ - tranzitii vom pastra notatia δ pentru
extensie pentru ca, ın general, δ(q, ǫ) 6= δ(q, ǫ) si
δ(q, a) 6= δ(q, a), a ∈ Σ.
δ(q, uv) = δ(δ(q, u), v), ∀q ∈ Q, ∀u, v ∈ Σ∗
LFAC (2019-20) Curs 3 6 / 25
Automate finite cu ǫ-tranzitii
Limbajul acceptat
Definitie 2
Limbajul acceptat (recunoscut) de automatul cu ǫ-tranzitii
A = (Q,Σ, δ, q0,F ) este multimea :
L(A) = {w |w ∈ Σ∗, δ(q0,w) ∩ F 6= ∅}.
Un cuvant w este recunoscut de un automat A daca, dupa citirea
ın ıntregime a cuvantului w , automatul (pornind din starea initiala
q0 ) poate sa ajunga ıntr-o stare finala.
LFAC (2019-20) Curs 3 7 / 25
Automate finite cu ǫ-tranzitii
Automatul determinist echivalent
Teorema 1
Pentru orice automat A cu ǫ - tranzitii exista un automat A′ determinist
echivalent cu A
Daca A = (Q,Σ, δ, q0,F ) atunci A′ = (Q′,Σ, δ′, q′0,F
′) unde:
Q′ = 2Q
q′0 = Cl(q0)
δ′(S, a) = Cl(⋃
s∈S δ(s, a)) S ∈ Q′, a ∈ Σ
S ∈ F ′ ⇔ S ∩ F 6= ∅
LFAC (2019-20) Curs 3 8 / 25
Automate finite cu ǫ-tranzitii
Automatul determinist echivalent
Teorema 1
Pentru orice automat A cu ǫ - tranzitii exista un automat A′ determinist
echivalent cu A
Daca A = (Q,Σ, δ, q0,F ) atunci A′ = (Q′,Σ, δ′, q′0,F
′) unde:
Q′ = 2Q
q′0 = Cl(q0)
δ′(S, a) = Cl(⋃
s∈S δ(s, a)) S ∈ Q′, a ∈ Σ
S ∈ F ′ ⇔ S ∩ F 6= ∅
Au loc:
δ′(q′0,w) = δ(q0,w), ∀w ∈ Σ∗
L(A′) = L(A)LFAC (2019-20) Curs 3 8 / 25
Automate finite cu ǫ-tranzitii
Automatul determinist echivalent - algoritmIntrare: Automatul A (cu ǫ - tranzitii) ; Cl(S)
Iesire: Automatul determinist A′ = (Q′,Σ, δ′, q′
0,F′), echivalent cu A.
q′
0 = Cl({q0}); 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, 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;
}LFAC (2019-20) Curs 3 9 / 25
Automate finite cu ǫ-tranzitii
Exemplu
LFAC (2019-20) Curs 3 10 / 25
Automate finite cu ǫ-tranzitii
Exemplu
LFAC (2019-20) Curs 3 10 / 25
Automatul determinist minimal
Curs 3
1 Automate finite cu ǫ-tranzitii
2 Automatul determinist minimal
LFAC (2019-20) Curs 3 11 / 25
Automatul determinist minimal
Stari accesibile
Fie A = (Q,Σ, δ, q0,F ) automat finit determinist
Starea q este accesibila ın A daca exista un cuvant w ∈ Σ∗ astfel ıncat
q = δ(q0,w).
LFAC (2019-20) Curs 3 12 / 25
Automatul determinist minimal
Stari inseparabile
Fie A = (Q,Σ, δ, q0,F ) un automat finit determinist.
Definitie 3
Starile q1 si q2 sunt inseparabile ın raport cu F , (notat q1ρq2) ddaca
∀w ∈ Σ∗ : δ(q1,w) ∈ F ⇔ δ(q2,w) ∈ F
LFAC (2019-20) Curs 3 13 / 25
Automatul determinist minimal
Stari inseparabile
Fie A = (Q,Σ, δ, q0,F ) un automat finit determinist.
Definitie 3
Starile q1 si q2 sunt inseparabile ın raport cu F , (notat q1ρq2) ddaca
∀w ∈ Σ∗ : δ(q1,w) ∈ F ⇔ δ(q2,w) ∈ F
Daca exista w ∈ Σ∗ cu δ(q1,w) ∈ F si δ(q2,w) 6∈ F (sau invers),
starile q1 si q2 sunt separabile (de catre w), si notam q1 sep q2
q1 sep q2 ⇔ ¬q1ρq2.
LFAC (2019-20) Curs 3 13 / 25
Automatul determinist minimal
Stari inseparabile
Fie A = (Q,Σ, δ, q0,F ) un automat finit determinist.
Definitie 3
Starile q1 si q2 sunt inseparabile ın raport cu F , (notat q1ρq2) ddaca
∀w ∈ Σ∗ : δ(q1,w) ∈ F ⇔ δ(q2,w) ∈ F
Daca exista w ∈ Σ∗ cu δ(q1,w) ∈ F si δ(q2,w) 6∈ F (sau invers),
starile q1 si q2 sunt separabile (de catre w), si notam q1 sep q2
q1 sep q2 ⇔ ¬q1ρq2.
Observatie: daca q1 ∈ F si q2 6∈ F , atunci q1 sep q2
LFAC (2019-20) Curs 3 13 / 25
Automatul determinist minimal
Exemplu
LFAC (2019-20) Curs 3 14 / 25
Automatul determinist minimal
Automat minimal
Observatii:
Relatia ρ este relatie de echivalenta.
∃a ∈ Σ : δ(p, a) sep δ(q, a) =⇒ p sep q.
LFAC (2019-20) Curs 3 15 / 25
Automatul determinist minimal
Automat minimal
Observatii:
Relatia ρ este relatie de echivalenta.
∃a ∈ Σ : δ(p, a) sep δ(q, a) =⇒ p sep q.
Teorema 2
Fie A un automat determinist cu toate starile accesibile. Daca toate
starile din A sunt separabile ın raport cu F, atunci nu exista un alt
automat A′ cu numar mai mic de stari si L(A) = L(A′).
LFAC (2019-20) Curs 3 15 / 25
Automatul determinist minimal
Automatul minimal
Fie A = (Q,Σ, δ, q0,F ) un automat finit determinist si relatia ρ.
Daca ∀q1, q2 ∈ Q : q1 sep q2, atunci A este minimal.
Altfel, automatul minimal:
Aρ = (Q/ρ,Σ, δρ, [q0],F/ρ)
Q/ρ - clasele de echivalenta ale relatiei ρ:
Q/ρ = {[q]|q ∈ Q}
δρ([q],a) = [δ(q,a)]
[q0] clasa de echivalenta ın care se afla starea q0
F/ρ = {[q]|q ∈ F}
LFAC (2019-20) Curs 3 16 / 25
Automatul determinist minimal
Exemplu
LFAC (2019-20) Curs 3 17 / 25
Automatul determinist minimal
Automatul minimal
Fie automatul minimal: Aρ = (Q/ρ,Σ, δρ, [q0],F/ρ)
Q/ρ - clasele de echivalenta ale relatiei ρ:
δρ([q], a) = [δ(q, a)]
[q0] clasa de echivalenta ın care se afla starea q0
F/ρ = {[q]|q ∈ F}
Teorema 3
Fie automatul determinist A, cu toate starile accesibile. Automatul Aρ
construit ca mai sus este automatul cu numar minim de stari care
accepta limbajul L(A).
LFAC (2019-20) Curs 3 18 / 25
Automatul determinist minimal
Algoritm pentru determinarea relatiei ρ
Fie A = (Q,Σ, δ, q0,F ), Q = {q0, q1, . . . , qn}
Tablou separabil[qi , qj ]:
separabil[qi ,qj ] = 1 ddaca qi sep qj (separabil[qi ,qj ] = 0 ddaca
qiρqj )
initial separabil[qi ,qj ] = 1 ddaca qi ∈ F ,qj 6∈ F (sau invers)
Pentru starile qi ,qj , daca exista a ∈ Σ cu δ(qi ,a), δ(qj ,a)
separabile, atunci qi , qj vor fi separarbile, adica :
daca separabil[qi ,qj ] = 0 si exista a ∈ Σ cu
separabil[δ(qi ,a), δ(qj ,a)] = 1, atunci separabil[qi ,qj ] = 1
LFAC (2019-20) Curs 3 19 / 25
Automatul determinist minimal
Algoritm pentru determinarea relatiei ρ
lista[p, r ] : (p 6= r )
definita pentru perechi de stari cu separabil[p, r ] = 0
LFAC (2019-20) Curs 3 20 / 25
Automatul determinist minimal
Algoritm pentru determinarea relatiei ρ
lista[p, r ] : (p 6= r )
definita pentru perechi de stari cu separabil[p, r ] = 0
lista[p, r ] = {(qi ,qj)|separabil[qi ,qj ] = 0 ∧ exista a ∈ Σ : p =
δ(qi ,a), r = δ(qj ,a), (qi ,qj) 6= (p, r)}
LFAC (2019-20) Curs 3 20 / 25
Automatul determinist minimal
Algoritm pentru determinarea relatiei ρ
Se initializeaza tabloul separabil (separabil[qi , qj ] = 1, daca
qi ∈ F , qj 6∈ F sau invers)
Pentru orice qi , qj (0 ≤ i < j ≤ n) cu separabil[qi , qj ] = 0 :
LFAC (2019-20) Curs 3 21 / 25
Automatul determinist minimal
Algoritm pentru determinarea relatiei ρ
Se initializeaza tabloul separabil (separabil[qi , qj ] = 1, daca
qi ∈ F , qj 6∈ F sau invers)
Pentru orice qi , qj (0 ≤ i < j ≤ n) cu separabil[qi , qj ] = 0 :
Daca exista a ∈ Σ cu separabil[δ(qi ,a), δ(qj ,a)] = 1, atunci:
separabil[qi , qj ] = 1
trebuie modificat tabloul separabil pentru toate perechile de stari a
caror separabilitate depinde de qi , qj (perechile de stari din
lista[qi , qj ])
LFAC (2019-20) Curs 3 21 / 25
Automatul determinist minimal
Algoritm pentru determinarea relatiei ρ
Se initializeaza tabloul separabil (separabil[qi , qj ] = 1, daca
qi ∈ F , qj 6∈ F sau invers)
Pentru orice qi , qj (0 ≤ i < j ≤ n) cu separabil[qi , qj ] = 0 :
Daca exista a ∈ Σ cu separabil[δ(qi ,a), δ(qj ,a)] = 1, atunci:
separabil[qi , qj ] = 1
trebuie modificat tabloul separabil pentru toate perechile de stari a
caror separabilitate depinde de qi , qj (perechile de stari din
lista[qi , qj ])
Altfel (pentru orice a ∈ Σ are loc separabil[δ(qi ,a), δ(qj ,a)] = 0):
pentru orice a ∈ Σ cu δ(qi , a) 6= δ(qj , a) adauga (qi , qj) la
lista[δ(qi , a), δ(qj , a)]
LFAC (2019-20) Curs 3 21 / 25
Automatul determinist minimal
Algoritm pentru determinarea relatiei ρ
//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. }
LFAC (2019-20) Curs 3 22 / 25
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. }
LFAC (2019-20) Curs 3 23 / 25
Automatul determinist minimal
Algoritm pentru determinarea relatiei ρ
// 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 );
}
}
LFAC (2019-20) Curs 3 24 / 25
Automatul determinist minimal
Exemplu
LFAC (2019-20) Curs 3 25 / 25
Automatul determinist minimal
Exemplu
LFAC (2019-20) Curs 3 25 / 25
Automatul determinist minimal
Exemplu
LFAC (2019-20) Curs 3 25 / 25
Automatul determinist minimal
Exemplu
LFAC (2019-20) Curs 3 25 / 25
Automatul determinist minimal
Exemplu
LFAC (2019-20) Curs 3 25 / 25
Automatul determinist minimal
Exemplu
LFAC (2019-20) Curs 3 25 / 25