1. DFA: DFA se referă la Automatul finit determinist. Se spune că un automat finit (FA) este determinist dacă corespunde unui simbol de intrare, există o singură stare rezultantă, adică există o singură tranziție. Un automat finit determinist este un set de cinci tupluri reprezentate ca,
Unde,
Î: Un set finit nevid de stări în controlul finit (qo, q1, q2, …).
Σ: Un set finit nevid de simboluri de intrare.
δ: Este o funcție de tranziție care ia două argumente, o stare și un simbol de intrare, returnează o singură stare.
qo: Este starea de pornire, una dintre stările din Q.
F: Este un set nevid de stări finale/stări de acceptare din setul aparținând lui Q.
2. CAUZE:
NFA se referă la automatul finit nondeterminist. Se spune că un automat finit (FA) este nedeterminist dacă există mai mult de o tranziție posibilă de la o stare pe același simbol de intrare.
Un automat finit nedeterminist este, de asemenea, un set de cinci tupluri și reprezentat ca,
Unde,
Î: Un set de stări finite nevide.
Σ: Un set de simboluri de intrare finite nevide.
δ: Este o funcție de tranziție care ia o stare de la Q și un simbol de intrare de la și returnează un subset de Q.
qo: starea inițială a NFA și membru al Q.
F: Un set nevid de stări finale și membru al Q.
Condiție prealabilă - Finite Automata
Diferența dintre DFA și NFA:
| DFA | NFA |
|---|---|
| DFA înseamnă Deterministic Finite Automata. | NFA înseamnă Nondeterministic Finite Automata. |
| Pentru fiecare reprezentare simbolică a alfabetului, există o singură tranziție de stare în DFA. | Nu este nevoie să specificați cum reacționează NFA în funcție de un simbol. |
| DFA nu poate folosi tranziția șir gol. | NFA poate folosi tranziția Empty String. |
| DFA poate fi înțeles ca o singură mașină. | NFA poate fi înțeles ca mai multe mașini mici care calculează în același timp. |
| În DFA, următoarea stare posibilă este setată în mod distinct. | În NFA, fiecare pereche de stare și simbol de intrare poate avea multe stări posibile următoare. |
| DFA este mai dificil de construit. | NFA este mai ușor de construit. |
| DFA respinge șirul în cazul în care acesta se termină într-o stare diferită de starea de acceptare. | NFA respinge șirul în cazul în care toate ramurile mor sau refuză șirul. |
| Timpul necesar pentru executarea unui șir de intrare este mai mic. | Timpul necesar pentru executarea unui șir de intrare este mai mare. |
| Toate DFA sunt NFA. | Nu toate NFA sunt DFA. |
| DFA necesită mai mult spațiu. | NFA necesită mai puțin spațiu decât DFA. |
| Configurația dead nu este permisă. de exemplu: dacă dăm intrare ca 0 pe starea q0, trebuie să dăm 1 ca intrare la q0 ca buclă de sine. | Configurația moartă este permisă. de exemplu: dacă dăm intrarea ca 0 pe starea q0, astfel putem da următoarea intrare 1 pe q1, care va trece la următoarea stare. |
| δ: QxΣ -> Q, adică următoarea stare posibilă aparține lui Q. | δ: Qx(Σ U ε) -> 2^Q, adică următoarea stare posibilă aparține setului de puteri Q. |
| Backtracking este permis în DFA. | Backtracking nu este întotdeauna posibil în NFA. |
| Conversia expresiei regulate în DFA este dificilă. | Conversia expresiei regulate în NFA este mai simplă în comparație cu DFA. |
| Mișcarea Epsilon nu este permisă în DFA | Mișcarea Epsilon este permisă în NFA |
| DFA permite o singură mișcare pentru un singur alfabet introdus. | Poate exista alegere (mai mult de o mișcare) pentru alfabetul cu o singură intrare. |