• La machine à états finis est utilisée pour reconnaître des modèles.
• La machine à automates finis prend la chaîne de symboles en entrée et change son état en conséquence. Dans l'entrée, lorsqu'un symbole souhaité est trouvé, la transition se produit.
• Pendant la transition, les automates peuvent soit passer à l’état suivant, soit rester dans le même état.
• FA a deux états : l’état d’acceptation ou l’état de rejet. Lorsque la chaîne d’entrée est traitée avec succès et que l’automate atteint son état final, il l’acceptera.

Un automate fini consiste à :

Q : ensemble fini d’états
∑ : ensemble fini de symboles d'entrée
q0 : état initial
F : état final
d : fonction de transition

La fonction de transition peut être définie comme

 δ: Q x ∑ →Q 

FA se caractérise de deux manières :

1. DFA (automates finis)
2. NDFA (automates finis non déterministes)

DFAE

DFA signifie Automates finis déterministes. Déterministe fait référence au caractère unique du calcul. Dans DFA, le caractère saisi ne passe qu'à un seul état. DFA n'accepte pas le déplacement nul, ce qui signifie que DFA ne peut pas changer d'état sans aucun caractère d'entrée.

DFA comporte cinq tuples {Q, ∑, q0, F, δ}

Exemple

Voir un exemple d'automates finis déterministes :

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

NDFA

NDFA fait référence aux automates finis non déterministes. Il est utilisé pour transiter par un nombre quelconque d'états pour une entrée particulière. NDFA accepte le mouvement NULL, ce qui signifie qu'il peut changer d'état sans lire les symboles.

NDFA a également cinq états identiques à DFA. Mais le NDFA a une fonction de transition différente.

La fonction de transition du NDFA peut être définie comme :

Exemple

Voir un exemple d'automates finis non déterministes :

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