• NFA signifie automates finis non déterministes. Il est plus facile de construire un NFA que un DFA pour un langage régulier donné.
• Les automates finis sont appelés NFA lorsqu’il existe de nombreux chemins pour une entrée spécifique de l’état actuel à l’état suivant.
• Chaque NFA n'est pas DFA, mais chaque NFA peut être traduit en DFA.
• NFA est défini de la même manière que DFA mais avec les deux exceptions suivantes, il contient plusieurs états suivants et contient une transition ε.

Dans l'image suivante, nous pouvons voir qu'à partir de l'état q0 pour l'entrée a, il y a deux états suivants q1 et q2, de même, à partir de q0 pour l'entrée b, les états suivants sont q0 et q1. Ainsi, il n'est pas fixé ni déterminé qu'avec une entrée particulière, où aller ensuite. Par conséquent, cet AF est appelé automates finis non déterministes.

Définition formelle de la NFA :

NFA comporte également cinq états identiques à DFA, mais avec une fonction de transition différente, comme indiqué ci-dessous :

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

où,

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

Représentation graphique d'un NFA

Un NFA peut être représenté par des digraphes appelés diagramme d'état. Dans lequel:

1. L'état est représenté par des sommets.
2. L'arc étiqueté avec un caractère d'entrée montre les transitions.
3. L'état initial est marqué par une flèche.
4. L'état final est désigné par le double cercle.

Exemple 1:

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

Solution:

Diagramme de transition :

Tableau de transition :

Dans le diagramme ci-dessus, nous pouvons voir que lorsque l'état actuel est q0, sur l'entrée 0, l'état suivant sera q0 ou q1, et sur 1 entrée, l'état suivant sera q1. Lorsque l'état actuel est q1, sur l'entrée 0 l'état suivant sera q2 et sur 1 entrée, l'état suivant sera q0. Lorsque l'état actuel est q2, sur l'entrée 0, l'état suivant est q2, et sur l'entrée 1, l'état suivant sera q1 ou q2.

Exemple 2 :

NFA avec ∑ = {0, 1} accepte toutes les chaînes avec 01.

Solution:

Tableau de transition :

Exemple 3 :

NFA avec ∑ = {0, 1} et accepte toutes les chaînes de longueur au moins 2.

Solution:

Tableau de transition :