- DFA se referă la automate finite deterministe. Deterministul se referă la unicitatea calculului. Automatele finite sunt numite automate finite deterministe dacă mașinii i se citește un șir de intrare câte un simbol.
- În DFA, există o singură cale pentru intrare specifică de la starea curentă la următoarea stare.
- DFA nu acceptă mutarea nulă, adică DFA nu poate schimba starea fără niciun caracter de intrare.
- DFA poate conține mai multe stări finale. Este folosit în analiza lexicală în compilator.
În diagrama următoare, putem vedea că din starea q0 pentru intrarea a, există o singură cale care merge la q1. În mod similar, de la q0, există o singură cale pentru intrarea b care merge la q2.
Definiția formală a DFA
Un DFA este o colecție de 5 tupluri, așa cum am descris-o în definiția FA.
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Funcția de tranziție poate fi definită ca:
δ: Q x ∑→Q
Reprezentarea grafică a DFA
Un DFA poate fi reprezentat prin digrafe numite diagramă de stare. In care:
- Starea este reprezentată prin vârfuri.
- Arcul etichetat cu un caracter de intrare arată tranzițiile.
- Starea inițială este marcată cu o săgeată.
- Starea finală este notă cu un cerc dublu.
Exemplul 1:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Soluţie:
Diagrama de tranziție:
Tabel de tranziție:
| Starea actuală | Următoarea stare pentru intrarea 0 | Următoarea stare de intrare 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q1 |
| *q2 | q2 | q2 |
Exemplul 2:
DFA cu ∑ = {0, 1} acceptă toate începând cu 0.
Soluţie:
obțineți lungimea matricei în c
Explicaţie:
- În diagrama de mai sus, putem vedea că pe data 0 ca intrare în DFA în starea q0, DFA își schimbă starea în q1 și merge întotdeauna la starea finală q1 la intrarea de pornire 0. Poate accepta 00, 01, 000, 001... .etc. Nu poate accepta niciun șir care începe cu 1, deoarece nu va ajunge niciodată la starea finală pe un șir care începe cu 1.
Exemplul 3:
DFA cu ∑ = {0, 1} acceptă toate care se termină cu 0.
Soluţie:
Explicaţie:
În diagrama de mai sus, putem vedea că la data 0 ca intrare în DFA în starea q0, DFA își schimbă starea în q1. Poate accepta orice șir care se termină cu 0, cum ar fi 00, 10, 110, 100....etc. Nu poate accepta niciun șir care se termină cu 1, deoarece nu va trece niciodată în starea finală q1 la 1 intrare, astfel încât șirul care se termină cu 1 nu va fi acceptat sau va fi respins.