TechCodeview

• NFA sta per automi finiti non deterministici. È facile costruire un NFA piuttosto che un DFA per un dato linguaggio regolare.
• Gli automi finiti sono chiamati NFA quando esistono molti percorsi per input specifici dallo stato corrente allo stato successivo.
• Ogni NFA non è DFA, ma ogni NFA può essere tradotto in DFA.
• NFA è definito allo stesso modo di DFA ma con le due eccezioni seguenti, contiene più stati successivi e contiene una transizione ε.

Nell'immagine seguente, possiamo vedere che dallo stato q0 per l'input a, ci sono due stati successivi q1 e q2, analogamente, da q0 per l'input b, gli stati successivi sono q0 e q1. Quindi non è fisso o determinato dove andare dopo con un input particolare. Quindi questo FA è chiamato automi finiti non deterministici.

Definizione formale di NFA:

Anche NFA ha cinque stati uguali a DFA, ma con diverse funzioni di transizione, come mostrato di seguito:

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

Dove,

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

Rappresentazione grafica di una NFA

Un NFA può essere rappresentato da digrafi chiamati diagrammi di stato. In quale:

esempio di sottostringa in Java

1. Lo stato è rappresentato dai vertici.
2. L'arco etichettato con un carattere di input mostra le transizioni.
3. Lo stato iniziale è contrassegnato da una freccia.
4. Lo stato finale è indicato dal doppio cerchio.

Esempio 1:

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

Soluzione:

Diagramma di transizione:

Tabella di transizione:

Nel diagramma sopra, possiamo vedere che quando lo stato corrente è q0, sull'ingresso 0, lo stato successivo sarà q0 o q1, e su 1 ingresso lo stato successivo sarà q1. Quando lo stato corrente è q1, sull'ingresso 0 lo stato successivo sarà q2 e sull'ingresso 1, lo stato successivo sarà q0. Quando lo stato corrente è q2, su 0 input lo stato successivo è q2 e su 1 input lo stato successivo sarà q1 o q2.

Esempio 2:

NFA con ∑ = {0, 1} accetta tutte le stringhe con 01.

Soluzione:

Tabella di transizione:

Esempio 3:

NFA con ∑ = {0, 1} e accetta tutte le stringhe di lunghezza almeno 2.

Soluzione:

Tabella di transizione: