Automate finite deterministe minimale [608299]

Automate finite deterministe minimale
Bogdan Macovei
6 Aprilie 2018
Abstract
Minimizarea automatelor finite deterministe reprezinta un instrument puternic in studiul general al
reprezentarii automatelor, intrucat acest proces permite vizualizarea limbajului in automate cu cel mai
mic numar posibil de stari, neredundante, ce faciliteaza intelegerea mai rapida a structurii limbajului
formal de la care s-a pornit.
Cuprins
Preliminarii algebrice 2
1.1 Relatii binare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Relatii binare de echivalenta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Clase de echivalenta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Multimea factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Preliminarii din teoria limbajelor formale 3
2.1 Definitia gramaticii regulate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Definirea automatului finit determinist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Multimea REG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Alte definitii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Constructia automatului minimal 5
3.1 Definirea aparatului matematic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Definitia automatului minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.3 Relatia de k-separabilitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Aplicatii 6
4.1 Constructia unui DFA minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.2 Minimizarea algoritmica a unui DFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1

Automate finite deterministe minimale
Preliminarii algebrice
1.1 Relatii binare
Numim relatie binara pe o multime Ao submultime a produsului cartezian A×A. Daca∼este acea relatie
binara (deci∼⊆A2=A×A), iar (a,b)∈∼, vom nota a∼bsi vom spune ca aeste in relatia∼cub. Pe o
multime cu nelemente exista 2n2relatii.
1.2 Relatii binare de echivalenta
Relatia∼se numeste relatie de echivalenta daca este:
1) reflexiva: a∼a,∀a∈A
2) simetrica: a∼b⇒b∼a,∀a,b∈A
3) tranzitiva: a∼bsib∼c⇒a∼c,∀a,b,c∈A
Exemplu :Relatia de congruenta modulo n pe Zeste relatie de echivalenta.
Demonstratie intuitiva :Fie≡n⊆Z2definita prin a≡nb⇔a(modn)=b(modn).
Atunci, este evident ca ≡neste reflexiva, pentru ca a≡nainseamna ca a=ain clasa de resturi mod n.
Dacaa≡nbeste evident si ca b≡na, intrucata=bimplicab=a, in orice clasa de resturi. Tranzivitatea
este, de asemenea, triviala, pentru ca se reduce la tranzitivitatea egalitatii a=bsib=cimplicaa=c, intr-o
clasa de resturi mod n. In concluzie, relatia binara ≡neste relatie de echivalenta. (Pentru o demonstratie
riguroasa, consultati Dumitrescu, T – Algebra 1 , Ed. Universitatii din Bucuresti, 2006, pg. 21, Teorema 14).
1.3 Clase de echivalenta
Fie∼⊆A2o relatie de echivalenta. Atunci, o clasa de echivalenta este reprezentata de multimea
[a] ={b∈A|b∼a}
De exemplu, pentru relatia ≡n⊆Z2, o clasa de echivalenta este [r], definita prin
[r] ={nq+r|q∈Z}
1.4 Multimea factor
Fie∼⊆A2o relatie de echivalenta. Atunci, multimea factor a acestei clase se noteaza A/∼si reprezinta
multimea formata din toate clasele de echivalenta ce se pot defini cu ajutorul relatiei ∼:
A/∼:={[a]|a∈A}
Pentru relatia≡n⊆Z2, multimea factor este data de
Z/≡n:={[r]|r∈Z}=Zn={[0],[1],…,[n]}
Observatie : Cand cardinalul multimii factor A/∼, notat|A/∼|<∞(este finit), spunem ca relatia de
echivalenta∼este o relatie de echivalenta de index finit .
Exemplu : Relatia de echivalenta modulo neste o relatie de echivalenta de index finit, intrucat |Zn|=n<∞.
2

Automate finite deterministe minimale
Preliminarii din teoria limbajelor formale
2.1 Definitia gramaticii regulate
Se numeste gramatica formala un cvadruplu G= (N,Σ,S,P )undeNeste multimea neterminalelor (sau a
variabilelor), Σeste multimea terminalelor, S∈Neste axioma (sau simbolul de start), iar Peste o relatie
binaraP⊆(N∪Σ)∗×(N∪Σ)∗, numita multimea regulilor de productie ale gramaticii. Se precizeaza faptul
caNsiΣsunt multimi finite si nevide.
Faptul ca (u,v)∈Pse noteazau→vsi se citeste “ utrece inv”. In acest sens, use numeste membrul stang
al productiei, iar vse numeste membrul drept al productiei.
Se numeste relatie de derivare intr −un pasfaptul ca un cuvant α∈Σ∗poate deveni β∈Σ∗aplicand o
productie, si se noteaza α⇒Gβ.
Daca:
1)α=α1uα2
2)β=α1vα2
3)(u→v)∈P
4)α1α2∈(N∪Σ)∗
atunci transformarea αinβinseamna trecerea de la α1uα2laα1vα2.
Notatia⇒kreprezinta aplicarea unei derivari de kori. Vom utiliza ⇒∗pentru a spune ca se va aplica o
derivare de 0 sau mai multe ori (inchiderea reflexiva si tranzitiva a lui ⇒), si⇒+pentru a spune ca se va
aplica o derivare cel putin o data (inchiderea tranzitiva).
⇒∗:=/uniondisplay
n≥0⇒n
⇒+:=/uniondisplay
n≥1⇒n
Se numeste gramatica regulata (sau de tip 3) o gramatica pentru care orice productie u→vare forma:
1)u∈N,
2)v∈Σ∗NΣ∗∪Σ∪{λ},
undeλeste cuvantul vid.
2.2 Definirea automatului finit determinist
Se numeste automat finit determinist un DFA M= (Q,Σ,δ,q 0,F)unde
1)Qeste multimea tuturor starilor,
2)Σeste multimea simbolurilor (alfabetul de intrare),
3)q0∈Qeste starea initiala,
4)F⊆Qeste multimea starilor finale,
5)δ:Q×Σ→Qreprezinta functia de tranzitie. Pe baza ei, definim functia δ∗:Q×Σ∗→Qcu
urmatoarea definitie recurenta:
i)δ∗(q,λ) =δ(q,λ) =q,
ii)δ∗(q,wa ) =δ(δ∗(q,w),a), q∈Q,w∈Σ∗,a∈Σ.
Limbajul acceptat de un DFA este
LDFA :={w∈Σ∗|δ∗(q0,w)∈F}
3

2.3 Multimea REG Automate finite deterministe minimale
2.3 Multimea REG
MultimeaREGreprezinta familia regulatelor, adica multimea tuturor limbajelor formale care sunt acceptate
de un automat finit sau de o gramatica regulata (sau de o expresie regulata, dar nu avem nevoie si de aceasta
definitie in finalizarea materialului propus).
FieG= (N,Σ,S,P )o gramatica regulata si DFA M= (Q,Σ,δ,q 0,F)un automat finit.
Atunci, putem defini familia regulatelor:
REG :={w∈Σ∗|S⇒∗
Gw}
REG :={w∈Σ∗|δ∗(q0,w)∈F}
(in cazul celei de-a doua definitii, consideram ca exista un DFA cu aceasta proprietate, iar acest DFA este
tocmai DFA Mfixat mai sus).
2.4 Alte definitii
FieL1siL2doua limbaje regulate. Atunci, se numeste cat stang al limbajului L2prinL1si se noteaza
L−1
1L2:={w∈Σ∗|∃u∈L1a.i. uw∈L2}.
Exemple :
1)a−1{ab,a,ba,abc}={b,λ,bc}
2){a,ba}−1{ab,ba2,a2,abc}={b,a,bc}
Intuitiv, aplicarea catului stang L−1
1L2inseamna sa eliminam prefixul din limbajele L2, unde prefixul este
dat de elementele ce apartin lui L1.
Observatie : Familia limbajelor regulate este inchisa la cat stang si cat drept cu limbaje oarecare.
4

Automate finite deterministe minimale
Constructia automatului minimal
Un DFAMse numeste minimal daca si numai daca orice automat echivalent cu el are cel putin cate stari are
automatul M. (i.e. este cel mai mic acceptor, in sensul cardinalului multimii starilor, |Q|, al unui limbaj
regulat dat)
3.1 Definirea aparatului matematic
Pentru∀L∈Σ∗definim relatia≡L⊆Σ∗×Σ∗, astfel cax≡Ly⇔x−1L=y−1L.
Observatii:
1)x≡Ly⇔∀v∈Σ∗avemxv∈L⇔yv∈L,
2)≡Leste relatie echivalenta pe Σ∗,
3)[x](mod≡L) =x−1L.
Teorema lui Myhill −Nerode: Un limbaj Leste regulat daca si numai daca ≡Leste o relatie de echivalenta
de index finit.
3.2 Definitia automatului minimal
Dat un limbaj regulat L, definim DFA MLa.i.L(ML) =L, unde
ML:= (Σ∗/≡L,Σ,δ,[λ](mod≡L),{[x]|x∈L})
deci
ML= ({x−1L|x∈Σ∗},Σ,δ,L,{x−1L|x∈L})
Unde functia de tranzitie δ:Q×Σ→Qeste definita prin δ(x−1L,a) =a−1(x−1L) = (xa)−1L.
In toata aceasta constructie, MLeste un DFA minimal .
3.3 Relatia de k-separabilitate
Fie DFAM= (Q,Σ,δ,q 0,F). Pentru∀k∈N, definim relatia≡kde k-separabilitate astfel:
≡k⊆Q2,p≡kq⇔∀w cu|w|≤k⇒δ∗(p,w)∈F⇔δ∗(q,w)∈F
Observatie :∀k∈N, relatia de k-separabilitate este o relatie de echivalenta pe Q.
5

Automate finite deterministe minimale
Aplicatii
In cele ce urmeaza voi ilustra doua aplicatii, una de constructie a unui automat finit determinist ce accepta
un limbaj regulat dat, folosind aparatul matematic definit anterior, si o alta de minimizare a unui automat
finit determinist deja construit, prin metode algoritmice bazate pe relatia de k-separabilitate a starilor.
4.1 Constructia unui DFA minimal
Fie dat limbajul regulat L={a2nbm|n,m≥1}. Sa se construiasca un DFA minimal care sa accepte cuvintele
dinL.
Solutie: Limbajul Ldat este garantat ca fiind un limbaj regulat, astfel ca ∃DFAM= (Q,Σ,δ,q 0,F)incat
L(M) =L, undeQeste multimea starilor, Σ ={a,b}este multimea terminalelor, δeste functia obisnuita de
tranzitie,q0este starea initiala iar F⊂Qeste multimea starilor finale.
Pe baza acestora, construim automatul minimal ML= (Σ∗/≡L,Σ,δ/prime,L,{x−1L|x∈L}), unde Σ∗/≡L=
{x−1L|x∈Σ∗}, iarδ/prime:Q×Σ→Q,δ/prime(x−1L,y) = (xy)−1L, undex−1L∈Σ∗/≡L,y∈Σ.
In cele ce urmeaza, vom descrie fiecare dintre elementele acestui cvintuplu (cu exceptia starii initiale, despre
care stim ca este Lsi a alfabetului utilizat, despre care stim ca este Σ).
Elementele lui Σ∗/≡L:
Avem ca Σ ={a,b}⇒ Σ∗={λ,a,b,a2,b2,…,ab,a2b,…,ab2,…}. A determina clasele de echivalenta x−1L,
inseamna a elimina, pe rand, toate prefixele limbajului care se gasesc in Σ∗, fara a crea redundanta.
(1)λ∈Σ∗, iar{λ}−1L=L.
(2)a∈Σ∗, iar{a}−1L={a2k−1bm|k,m≥1}=aimpb+cu semnificatia faptului ca impla indice reprezinta
o prescurtare pentru ala putere impara. Din cauza faptului ca aimpnu este un prefix valid al limbajului
in contextul continuarii prin citire de caractere b, pentru ca ar mai fi necesara citirea unui numar de
a-uri pana cand avem un numar par, inseamna ca starea curenta este suficient exprimata prin aimp,
neglijand total existenta b-urilor.
(3)a2∈Σ∗, iar{a2}−1Leste, analog cazului de mai sus, starea aparb+. Observam ca daca am continua cu
a3,a4,…, am obtine tot aceleasi doua stari, deci ar fi redundanta.
Observatie : Deoarece nu avem garantia faptului ca am terminat de citit caracterele ain momentul in care
suntem in starea aparb+, vom permite citirea, in continuare, a a-urilor, astfel ca vom avea starile echivalente
apar≡aparb+. (nu strica structura limbajului, ci permite recitirea unui numar par de caractere apana sa se
treaca la citirea caracterelor b)
(4)b∈Σ∗, iar{b}−1L={bm−1|m≥1}, o stare care nu este momentan accesibila, pentru ca limbajul
incepe cu cel putin doua caractere a, ceea ce ne conduce la starea
(5)(a2)nb∈Σ∗, iar{(a2)nb}−1L={bm−1|m≥1}=b∗, adica starea in care vom ajunge dupa ce am
consumat toate a-urile. Starile sunt suficiente, pentru ca citirea unui numar suplimentar de terminale b
conduce tot la aceasta stare.
Pana in acest moment, am gasit ca multimea starilor automatului minimal este:
Σ∗/≡L=/braceleftbig
{λ}−1L=L,aimp,apar≡aparb+,b∗/bracerightbig
deci cardinalul starilor automatului minimal este |Σ∗/≡L|= 4.
Elementele lui F :
Avem ca multimea starilor finale este data de x−1Lcandx∈L, iar asta inseamna, de fapt, a elimina toate
prefixele lui Lcare se gasesc strict ca elemente in limbaj.
Observam ca, in acest caz, limbajul Lcontine, ca cel mai mic element in sens lexicografic, pe a2bdeci, in
sens general, un prefix de forma a2kb,k∈N. Pentru a putea citi macar un terminal b, suntem nevoiti sa
6

4.2 Minimizarea algoritmica a unui DFA Automate finite deterministe minimale
consumam toate a-urile, deci vom obtine ca starea finala este {a2nb}−1L={bm−1|m≥1}=b∗, iar aceasta
este si unica stare finala, intrucat citirea unui numar mai mare de caractere bdupa consumarea a-urilor
conduce la redundanta (se va obtine mereu b∗).
Avem, astfel:
{x−1L|x∈L}={b∗}
Functiaδ/prime:
Vom aplica definitia functiei δ/prime, luand fiecare stare din Σ∗/≡Lcu fiecare litera din Σ.
(1.a)δ/prime({λ}−1L,a) ={a}−1L=aimppentru ca o stare a1⊆aimp,
(1.b)δ/prime({λ}−1L,b) ={b}−1L/negationslash∃, pentru ca suntem obligati sa citim macar doua caractere a,
(2.a)δ/prime({aimp}−1L,a) = (aimpa)−1L=apar,
(2.b)δ/prime({aimp}−1L,b)/negationslash∃, pentru ca nu se permite tranzitie cu un bdupa un numar impar de a-uri,
(3.a)δ/prime({apar}−1L,a) = (apara)−1L=aimp, aici observam ca am folosit echivalenta apar≡aparb+, citind in
continuarea-uri nu puteam efectua o tranzitie dintr-o stare in care limbajul a obtinut deja cuvinte cu sufixul
b,
(3.b)δ/prime({aparb+}−1L,b) = (aparb+b)−1L=b∗, pentru ca plecarea din starea aparb+garanteaza finalizarea
citirii corecte a a-urilor,
(4.a)δ/prime({b∗}−1L,a)/negationslash∃, pentru ca nu exista niciun cuvant cu prefixul b∗ain limbajul L, iar
(4.b)δ/prime({b∗}−1L,b) =b∗, adica pot fi efectuate oricate tranzitii cu citirea de caractere b.
Concluzie : In acest moment, am descris complet automatul finit determinist MLcare accepta cuvintele din
limbajul dat Lsi care, din constructia algebrica pe care am oferit-o, este minimal cu aceasta proprietate.
4.2 Minimizarea algoritmica a unui DFA
Fie dat urmatorul automat finit determinist complet DFA M= (Q,Σ,δ,q 0,F)astfel incat:
1)Q={q0,q1,q2,q3,q4,q5,q6},
2)Σ ={a,b},
3)q6∈F,
4) iar functia δeste data de urmatorul tabel:
Stareδ(q,a)δ(q,b)
q0q1q3
q1q3q2
q2q3q2
q3q6q5
q4q6q5
q5q6q2
q6q4q5
Vom aplica procedeul de k-separabilitate in maniera urmatoare:
1) separam starile finale de cele nefinale in doua multimi, A0=Q−FsiB0=F;
2) scriem pentru fiecare stare in parte carei multimi ii apartine;
3)separam starile pentru care tranzitiile cu asibduc in multimi diferite, si denumim aceste multimi A1,
B1, …;
4) aplicam acesti pasi pana cand nu mai putem separa starile.
7

4.2 Minimizarea algoritmica a unui DFA Automate finite deterministe minimale
Starile ce raman in aceeasi partitie sunt stari echivalente.
Pasul 1:
Stareδ(q,a)δ(q,b)
q0∈A0q1∈A0q3∈A0
q1∈A0q3∈A0q2∈A0
q2∈A0q3∈A0q2∈A0
q3∈A0q6∈B0q5∈A0
q4∈A0q6∈B0q5∈A0
q5∈A0q6∈B0q2∈A0
q6∈B0q4∈A0q5∈A0
Pasul 2:
Separam acum starile care nu merg in aceleasi multimi cu tranzitiile functiei δ. De exemplu, starile q0,q1,q2
ajung, prin intermediul functiei δin aceleasi multimi cu asib, fata de starile q3,q4,q5. Astfel, primele 3 stari
vor fi in multimea A1, urmatoarele stari in multimea B1, iar starea q6va trece in multimea C1.
Stareδ(q,a)δ(q,b)
q0∈A1q1∈A1q3∈B1
q1∈A1q3∈B1q2∈A1
q2∈A1q3∈B1q2∈A1
q3∈B1q6∈C1q5∈B1
q4∈B1q6∈C1q5∈B1
q5∈B1q6∈C1q2∈A1
q6∈C1q4∈B1q5∈B1
Pasul 3:
Separam din nou, si observam ca:
1) stareaq0va fi separata, pentru ca are tranzitii in multimile A1siB1,
2)starileq1siq2vor fi in aceeasi partitie, intrucat ambele au tranzitii in multimile B1siA1(conteaza
ordinea lor, din aceasta cauza nu sunt partitionate la comun cu q0),
3)q3siq4vor fi in aceeasi partitie, avand tranzitii in multimile C1siB1,
4)q5va fi intr-o partitie separata,
5) la fel siq6.
Avem, acum:
Stareδ(q,a)δ(q,b)
q0∈A2q1∈B2q3∈C2
q1∈B2q3∈C2q2∈B2
q2∈B2q3∈C2q2∈B2
q3∈C2q6∈E2q5∈D2
q4∈C2q6∈E2q5∈D2
q5∈D2q6∈E2q2∈B2
q6∈E2q4∈C2q5∈D2
In acest moment, toate starile sunt partitionate in submultimi ce nu mai pot fi divizate, intrucat au tranzitii
cu terminalele asibin aceleasi multimi (in cadrul unei partitii).
Astfel, starile q1siq2sunt echivalente, deci q1≡q2≡q12, analog siq3≡q3≡q34, iar automatul minimal va
fi:
ML= (Q/prime={q0,q12,q34,q5,q6},Σ ={a,b},δ/prime,q0,F={q6})
8

4.2 Minimizarea algoritmica a unui DFA Automate finite deterministe minimale
unde functia de tranzitie δ/primea automatului minimal este:
Stareδ(q,a)δ(q,b)
q0q12q34
q12q34q12
q34q6q5
q5q6q12
q6q34q5
9