Minimizarea automatului

Prin minimizarea unui automat înțelegem găsirea unui automat echivalent care conține numărul minim posibil de stări. Chiar și un automat care nu conține nicio stare neproductivă poate fi simplificat în continuare.

Exemplu

Să luăm acest automat:

Automatul acceptă doar cuvintele 01 și 11. Este evident că există un automat mai simplu, cu trei stări, care acceptă același limbaj. Stările q₁ și q₂ pot fi îmbinate într-o singură stare nouă {q₁, q₂}, iar tranzițiile care duceau în stările q₁ sau q₂ vor duce în noua stare, la fel și tranzițiile care porneau din q₁ și q₂. Obținem acest automat:

Acest automat acceptă, în mod evident, același limbaj ca cel anterior și are în plus mai puține stări.

Echivalența stărilor

Fie un automat A = ⟨Q, Σ, δ, q₀, F⟩. Definim limbajul stării q ∈ Q, pe care îl notăm L(q), astfel:

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Adică schimbăm starea inițială a automatului A din q₀ în q și aflăm limbajul acceptat de acest automat. Cu alte cuvinte, în limbajul L(q) se află toate cuvintele w pentru care, în automatul A, ajungem din starea q cu cuvântul w într-o stare finală a automatului. Dacă ne întoarcem la automatul anterior, avem L(q₁) = {1}.

Spunem că două stări diferite q₁ și q₂ sunt echivalente dacă

$L (q_{1}) = L (q_{2})$

Ce înseamnă asta? Dacă stările q₁, q₂ sunt echivalente, atunci, dacă le facem stări inițiale ale automatului, vor genera același limbaj. Cu alte cuvinte: dacă automatul ajunge în configurațiile ⟨q₁, w⟩ și ⟨q₂, w⟩, atunci trebuie fie să accepte în ambele cazuri, fie să respingă în ambele cazuri.

Dacă ne întoarcem la automatul anterior: stările q₁ și q₂ sunt echivalente, deoarece, dacă ne aflăm în starea q₁, putem accepta cuvântul de intrare doar dacă partea necitită a cuvântului este egală cu 1. La fel, dacă ne aflăm în starea q₂.

La minimizarea unui automat este deci vorba despre găsirea stărilor echivalente și eliminarea lor prin îmbinarea într-o singură stare nouă, la fel cum am făcut în exemplul de mai sus.

Cum găsim stările echivalente

Ce stări cu siguranță nu vor fi echivalente? Dacă luăm o stare finală și una nefinală, ele cu siguranță nu vor fi echivalente, deoarece limbajul stării finale este diferit de limbajul stării nefinale – starea finală acceptă cu siguranță cuvântul ε, cea nefinală nu. Vom arăta procedeul direct pe un exemplu. Fie acest automat:

Începem prin a crea două mulțimi de stări

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Acum creăm tabelul tranzițiilor și păstrăm informația despre grupele S₁ și S₂:

$\begin{array}{ccccc} grupa & starea & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Acum modificăm tabelul astfel încât, în loc să scriem direct în ce stări se ajunge pentru un simbol dat, să notăm doar grupa în care trecem. De exemplu, din starea q₃ ajungem pentru 0 în starea q₅, care este în grupa S₂. În loc de q₅ scriem deci în tabel S₂:

$\begin{array}{ccccc} grupa & starea & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Acum împărțim în continuare ambele grupe. În aceeași grupă punem mereu stările care trec în aceleași grupe pentru toate simbolurile. De exemplu, stările q₃ și q₆ nu vor fi în aceeași grupă, deoarece nici pentru 0, nici pentru 1 nu merg în aceeași grupă. În schimb, stările q₁ și q₂ vor fi în aceeași grupă, deoarece ambele stări nu au tranziție pentru 0 și ambele merg pentru 1 în grupa S₁. Creăm astfel grupe noi:

$\begin{array}{ccccc} grupa & starea & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

În fiecare grupă avem aceleași tranziții. Notăm grupele nou apărute și aflăm din nou în care dintre aceste grupe noi duc stările:

$\begin{array}{ccccc} grupa & starea & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

În acest moment am face o nouă împărțire a grupelor. Vedem însă că nu mai putem face nicio împărțire, am obține aceleași grupe – deoarece stările q₁ și q₂ au, e drept, aceleași tranziții între grupe, dar sunt deja în aceeași grupă și nu mai există nicio altă stare în grupa S₄. Algoritmul de căutare a stărilor echivalente s-a încheiat. Din fiecare grupă este suficient să alegem o stare, pe celelalte le ștergem, iar toate tranzițiile care duceau în stările șterse vor duce în singura stare pe care am ales-o.

Putem alege astfel ca noul nostru automat să aibă stările q₃, q₆, q₀, q₁, q₄, iar stările q₂ și q₅ să le eliminăm. Toate tranzițiile care duceau în q₂ vor duce acum în q₁, iar toate tranzițiile care duceau în q₅ vor duce în q₄:

Procedeul de minimizare a automatului

Eliminăm stările inaccesibile,
eliminăm stările neproductive,
eliminăm stările echivalente.

Surse

Capitole: Stări inaccesibile, Stări neproductive, Minimizarea automatului

« Anterior: Stări neproductive

Următor: Limbaje regulate »