Automat finit

Automatul finit (în engleză finite state machine sau finite automaton) este un model de calcul al unui calculator primitiv, alcătuit din mai multe stări și mai multe tranziții, care poate accepta sau respinge un cuvânt dat.

Exemplu

Vom descrie informal un automat finit cu ajutorul unei diagrame de stări:

Automatul este alcătuit din stări; în figură sunt trei stări rotunde, q₀, q₁ și q₂. Între aceste stări există tranziții, adică săgețile. În automat trebuie să existe și o stare inițială, aici starea q₀. Starea inițială se reprezintă adesea printr-o săgeată care intră în ea și care nu pleacă din nicio stare. În plus, în automat există de obicei o stare finală, pe care o desenăm cu linie dublă; în figură este starea q₂.

Un automat construit astfel acceptă anumite cuvinte. Introducem în automat un cuvânt, iar automatul încearcă să-l accepte. Dacă îl acceptă, răspunde DA, dacă nu îl acceptă, răspunde NU. Automatul nostru încearcă să accepte cuvinte formate din literele „a, b, c”, așa că putem încerca să acceptăm cuvântul „abbc”.

Începem în starea inițială q₀, iar la intrare avem cuvântul „abbc”. Mai departe urmăm săgețile.

Cuvântul îl parcurgem în mod obișnuit de la stânga la dreapta, adică primul simbol pe care îl luăm este „a”. Săgeata pentru intrarea „a” duce în starea q₁, așa că trecem acolo și eliminăm simbolul „a” din cuvânt. La intrare ne-a rămas cuvântul „bbc”:

Săgeata pentru intrarea „b” duce înapoi în nodul q₁. Eliminăm din nou prima literă, iar la intrare avem cuvântul „bc”. Rămânem din nou în starea q₁. La final avem la intrare cuvântul „c”. Din starea q₁, săgeata pentru intrarea „c” ne duce în starea q₂.

Am consumat toate literele cuvântului de intrare și ne aflăm în starea q₂, care este stare finală. Acest automat finit acceptă deci cuvântul „abbc”.

Dacă la final nu ne-am afla într-o stare de acceptare, automatul nu ar accepta cuvântul. La fel, automatul nu ar accepta cuvântul nici dacă într-o anumită stare nu am avea unde să mergem. De exemplu, pentru intrarea „ab” am ajunge în starea q₁ și ne-am opri acolo – automatul nu acceptă un astfel de cuvânt. Dacă am testa cuvântul „aabbc”, am avea din nou ghinion, pentru că din starea q₁ nu pleacă nicio săgeată pentru litera „a”.

Automatul finit servește deci la recunoașterea unei mulțimi de cuvinte. În practică, am putea folosi un automat, de exemplu, pentru a afla dacă un cuvânt de intrare este o adresă de email validă.

Definiția automatului finit

Imaginea intuitivă de mai sus despre ce este un automat finit trebuie formalizată, pentru a putea lucra cu automatele mai departe și mai bine.

Spunem că un automat finit (determinist) (AFD) este un cvintuplu ⟨Q, Σ, δ, q₀, F⟩, unde

• Q este o mulțime finită de stări,
• Σ (sigma mare) este alfabetul (mulțime finită de simboluri/litere),
• δ: Q × Σ ⟶ Q este funcția de tranziție,
• q₀ ∈ Q este starea inițială,
• F ⊆ Q este mulțimea stărilor finale (de acceptare).

Dacă ne întoarcem la automatul de mai sus,

putem spune că în mulțimea de stări Q sunt trei stări, Q = {q₀, q₁, q₂}. Alfabetul Σ conține literele din care putem forma cuvinte pe care automatul le va accepta sau le va respinge. Aici este probabil alfabetul Σ= {a, b, c}, dar poate fi și orice supramulțime a lui. Starea inițială q₀ este starea q₀, aici nu se schimbă nimic. Mulțimea stărilor finale are în acest automat o singură stare, F = {q₂}.

Prin funcția de tranziție înțelegem cele trei săgeți cu litere. Dacă notația δ: Q × Σ ⟶ Q te încurcă, ea înseamnă doar că δ este o funcție (sau, mai bine zis, o aplicație) care primește doi parametri: o stare din Q și o literă din Σ. Când o apelăm, funcția returnează o stare nouă. Funcția noastră de tranziție am putea-o defini printr-un tabel astfel:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Dacă apelăm deci δ(q₁, c), aplicăm a treia linie, iar funcția răspunde cu starea q₂ – la fel ca diagrama. Dacă ne aflăm în starea q₁ și la intrare este litera „c”, ajungem în starea q₂. Înainte să definim formal ce înseamnă că automatul acceptă un cuvânt, ne vom baza pe înțelegerea intuitivă a acestei noțiuni și vom arăta câteva exemple în plus.

Alte exemple

1. Construiește un automat care lucrează peste alfabetul binar, adică Σ= {0, 1}, și acceptă doar cuvintele care se termină cu 1. De exemplu, acceptă cuvintele 1, 01, 000001, 0101011.

   

   Automatul nostru are două stări – cea inițială q₀ și cea finală q₁. Ori de câte ori avem la intrare cifra 1, trecem în starea finală q₁ și rămânem în ea. Dimpotrivă, dacă la intrare este cifra 0, trecem în starea nefinală q₀ și rămânem de asemenea în ea.

2. Construiește un automat peste alfabetul binar care acceptă doar cuvintele a căror primă literă este diferită de ultima literă.

   

   Chiar din primul pas, automatul se împarte în două „subautomate”. Dacă cuvântul începe cu zero, automatul intră în partea stângă și rămâne acolo; dacă începe cu unu, trece în partea dreaptă. Apoi totul este obișnuit: dacă ne aflăm în partea stângă și la intrare este 1, trecem în starea finală și rămânem în ea. Dacă la intrare este 0, trecem în starea q₁, care nu este finală.

   Spre deosebire de automatele anterioare, acest automat are mai multe stări finale, adică F = {q₃, q₄}.

3. Construiește un automat peste alfabetul binar care acceptă doar cuvintele ce nu conțin două zerouri consecutive.

   

   Acest automat este interesant din două motive: primul este că acceptă cuvântul vid. Putem încerca să introducem în automat cuvântul vid, iar automatul îl acceptă dacă starea inițială este în același timp stare finală, ceea ce se întâmplă la acest automat. Deoarece cuvântul vid este un cuvânt care nu conține două zerouri consecutive, rezultatul este cel corect. Altă particularitate este că acest automat are toate stările finale. Singurul caz în care automatul nu ar accepta un cuvânt este când dintr-o stare nu pleacă nicio tranziție. Asta se întâmplă în starea q₁, care nu are tranziție pentru 0, pentru că altfel cuvântul ar conține două zerouri consecutive.

4. Construiește un automat peste alfabetul {-,+,.,0,1,…,9} care acceptă doar cuvintele ce reprezintă un număr. Adică fie un număr întreg, de exemplu 2, 548, 98263, fie un număr zecimal, de exemplu 5584.48, 3.14, și ambele și în varianta negativă, cu semnul minus -2, -548, -3.14, precum și cu plus scris explicit, adică +2, +548, +3.14. În același timp, trebuie să putem scrie numărul 0.123 doar ca .123 (fără zero la început), inclusiv cu ambele semne. Vom introduce o notație auxiliară: în loc să scriem zece tranziții pentru cele zece cifre, vom folosi simbolul N.

   

5. Construiește un automat peste alfabetul binar care acceptă doar cuvintele de forma 0ⁿ1ⁿ, adică cuvintele au la început un anumit număr de zerouri, urmat de același număr de cifre 1. Exemple de astfel de cuvinte sunt 0011, 00001111, 01.

   Un astfel de automat nu se poate construi, pentru că nu avem nicăieri cum să „ținem minte” numărul de zerouri. Ar trebui să creăm mai multe „subautomate”, ca în al doilea exemplu, dar ar fi nevoie de o infinitate de „subautomate”, câte unul pentru fiecare valoare a lui n.

Formalizarea calculului automatului

Am definit deja formal automatul finit în sine. În continuare trebuie să definim ce face de fapt un astfel de automat, adică definim calculul automatului.

Configurația automatului: Spunem că perechea ⟨q, w⟩ ∈ Q × Σ^∗ este o configurație a automatului, unde q este starea curentă în care se află automatul, iar w este partea din cuvânt care nu a fost încă citită. Σ^∗ este închiderea alfabetului Σ, mulțimea tuturor cuvintelor care se pot forma cu literele alfabetului Σ. Din închidere face parte și cuvântul vid, pe care îl notăm ε.

Dacă avem automatul ⟨Q, Σ, δ, q₀, F⟩ și încercăm să acceptăm cuvântul w, atunci automatul se află în configurația inițială ⟨q₀, w⟩. Dacă ne întoarcem la automatul

și vrem să acceptăm cuvântul w = abbc, configurația inițială va fi ⟨q₀, abbc⟩.

Pasul de calcul îl definim ca o relație ↦ între mulțimile (Q × Σ^∗) × (Q × Σ^∗), adică între configurațiile automatului. Fie w = w₀w₁… w_n partea încă necitită a cuvântului w. Atunci spunem că perechile ⟨q₁, w₀w₁… w_n⟩ și ⟨q₂, w₁… w_n⟩ sunt în relația ↦, ceea ce scriem

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

dacă și numai dacă δ(q₁, w₀) = q₂. Revenind la exemplul nostru, configurația inițială este ⟨q₀, abbc⟩. Din diagramă vedem că pentru intrarea „a” ne putem deplasa în starea q₁. Putem deci scrie

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

deoarece δ(q₀, a) = q₁. Am făcut astfel un pas de calcul – ne-am uitat în ce stare ar trebui să mergem pentru intrarea dată (= prima literă din partea încă necitită a cuvântului), am trecut acolo și am eliminat prima literă din partea necitită a cuvântului. Am obținut astfel o nouă configurație.

Închiderea reflexivă și tranzitivă a relației pas de calcul o notăm ↦ ^∗. Dacă scriem K₁ ↦ ^∗ K₂, unde K₁, K₂ sunt configurații ale automatului, înseamnă că din configurația K₁ putem ajunge, prin mai mulți pași de calcul, în configurația K₂, adică există un șir finit de configurații astfel încât:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

De exemplu, în automatul nostru are loc ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, pentru că după doi pași de calcul ne rămâne cuvântul „bc” și rămânem în starea q₁. Adică există acest șir de configurații:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

Automatul acceptă cuvântul w dacă și numai dacă există q_f ∈ F astfel încât $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Asta înseamnă că automatul acceptă cuvântul w dacă și numai dacă există un șir de pași de calcul astfel încât la sfârșitul șirului am citit tot cuvântul și ne aflăm într-o stare finală a automatului. Faptul că am citit tot cuvântul este exprimat prin aceea că în configurație, în locul cuvântului, se află ε, adică cuvântul vid. Automatul nostru acceptă cuvântul abbc, deoarece există acest șir de configurații:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

iar starea q₂ este stare finală, q₂ ∈ F.

Limbajul recunoscut de automat este mulțimea tuturor cuvintelor pe care automatul le acceptă. Limbajul automatului A îl notăm L(A). Are loc L(A) ⊆ Σ^∗ și

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }|A\text{ acceptă cuvântul }w\}$$

Limbajul regulat este un limbaj care este recunoscut de un automat finit.

Două automate finite sunt echivalente dacă recunosc același limbaj. Adică automatele A₁ și A₂ sunt echivalente dacă L(A₁) = L(A₂).

Surse

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools