TechCodeview

• NFA oznacza niedeterministyczne automaty skończone. Łatwo jest skonstruować NFA niż DFA dla danego języka regularnego.
• Automaty skończone nazywane są NFA, gdy istnieje wiele ścieżek dla określonych danych wejściowych od stanu bieżącego do stanu następnego.
• Każdy NFA nie jest DFA, ale każdy NFA można przełożyć na DFA.
• NFA jest definiowane w taki sam sposób jak DFA, ale z następującymi dwoma wyjątkami, zawiera wiele kolejnych stanów i zawiera przejście ε.

Na poniższym obrazku widać, że ze stanu q0 dla wejścia a wychodzą dwa kolejne stany q1 i q2, analogicznie ze stanu q0 dla wejścia b kolejnymi stanami są q0 i q1. Zatem nie jest ustalone ani określone, gdzie iść dalej w przypadku konkretnych danych wejściowych. Stąd ten FA nazywa się niedeterministycznymi automatami skończonymi.

Formalna definicja NFA:

NFA ma również pięć stanów takich samych jak DFA, ale z inną funkcją przejścia, jak pokazano poniżej:

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

Gdzie,

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

Graficzne przedstawienie NFA

NFA można przedstawić za pomocą dwuznaków zwanych diagramami stanu. W którym:

1. Stan jest reprezentowany przez wierzchołki.
2. Łuk oznaczony znakiem wejściowym pokazuje przejścia.
3. Stan początkowy zaznaczony jest strzałką.
4. Stan końcowy jest oznaczony podwójnym kółkiem.

Przykład 1:

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

Rozwiązanie:

Schemat przejścia:

Tabela przejściowa:

Na powyższym schemacie widzimy, że gdy aktualny stan wynosi q0, na wejściu 0 następnym stanem będzie q0 lub q1, a na 1 wejściu kolejnym stanem będzie q1. Gdy bieżący stan to q1, na wejściu 0 następnym stanem będzie q2, a na wejściu 1 następnym stanem będzie q0. Gdy bieżący stan to q2, na wejściu 0 następnym stanem będzie q2, a na wejściu 1 następnym stanem będzie q1 lub q2.

Przykład 2:

NFA z ∑ = {0, 1} akceptuje wszystkie ciągi z 01.

Rozwiązanie:

Tabela przejściowa:

Przykład 3:

NFA z ∑ = {0, 1} i akceptuj cały ciąg o długości co najmniej 2.

Rozwiązanie:

Tabela przejściowa: