TechCodeview

• NFA înseamnă automate finite nedeterministe. Este ușor să construiți un NFA decât DFA pentru un anumit limbaj obișnuit.
• Automatele finite sunt numite NFA atunci când există multe căi pentru intrare specifică de la starea curentă la starea următoare.
• Fiecare NFA nu este DFA, dar fiecare NFA poate fi tradus în DFA.
• NFA este definit în același mod ca DFA, dar cu următoarele două excepții, conține mai multe stări următoare și conține tranziția ε.

În imaginea următoare, putem vedea că din starea q0 pentru intrarea a, există două stări următoare q1 și q2, în mod similar, din q0 pentru intrarea b, următoarele stări sunt q0 și q1. Astfel, nu este fixat sau determinat că, cu o anumită intrare, unde să mergem mai departe. Prin urmare, acest FA se numește automate finite nedeterministe.

Definiția oficială a NFA:

NFA are, de asemenea, cinci stări la fel ca DFA, dar cu funcție de tranziție diferită, după cum se arată în continuare:

 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup> 

Unde,

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Reprezentarea grafică a unui NFA

Un NFA poate fi reprezentat prin digrafe numite diagramă de stare. In care:

1. Starea este reprezentată prin vârfuri.
2. Arcul etichetat cu un caracter de intrare arată tranzițiile.
3. Starea inițială este marcată cu o săgeată.
4. Starea finală este notată de cerc dublu.

Exemplul 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

Soluţie:

Diagrama de tranziție:

Tabel de tranziție:

În diagrama de mai sus, putem vedea că atunci când starea curentă este q0, la intrarea 0, următoarea stare va fi q0 sau q1, iar la 1 intrare următoarea stare va fi q1. Când starea curentă este q1, pe intrarea 0 următoarea stare va fi q2 și pe 1 intrare, următoarea stare va fi q0. Când starea curentă este q2, la intrarea 0 următoarea stare este q2, iar la intrarea 1 următoarea stare va fi q1 sau q2.

Exemplul 2:

NFA cu ∑ = {0, 1} acceptă toate șirurile cu 01.

Soluţie:

Tabel de tranziție:

Exemplul 3:

NFA cu ∑ = {0, 1} și acceptă toate șirurile de lungime de cel puțin 2.

Soluţie:

Tabel de tranziție: