limbaje formale, automate si compilatoareotto/lfac2019-20/lfac3.pdflimbaje formale, automate s¸i...

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



LFAC (2019-20) Curs 3 3 / 25



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


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


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


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


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


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


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


Exemplu

LFAC (2019-20) Curs 3 10 / 25

Automatul determinist minimal

Curs 3



LFAC (2019-20) Curs 3 11 / 25


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


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


Stari inseparabile


Definitie 3


∀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


Stari inseparabile


Definitie 3


∀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


Exemplu

LFAC (2019-20) Curs 3 14 / 25


Automat minimal

Observatii:

Relatia ρ este relatie de echivalenta.

∃a ∈ Σ : δ(p, a) sep δ(q, a) =⇒ p sep q.

LFAC (2019-20) Curs 3 15 / 25


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 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


Exemplu

LFAC (2019-20) Curs 3 17 / 25


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


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



lista[p, r ] : (p 6= r )

definita pentru perechi de stari cu separabil[p, r ] = 0

LFAC (2019-20) Curs 3 20 / 25



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



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






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






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



//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


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



// 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


Exemplu

LFAC (2019-20) Curs 3 25 / 25

limbaje formale, automate si compilatoareotto/lfac2019-20/lfac3.pdflimbaje formale, automate s¸i...

Documents