• La màquina d'estats finits s'utilitza per reconèixer patrons.
• La màquina d'autòmats finits pren la cadena de símbol com a entrada i canvia el seu estat en conseqüència. A l'entrada, quan es troba un símbol desitjat, es produeix la transició.
• Durant la transició, els autòmats poden passar al següent estat o romandre en el mateix estat.
• FA té dos estats: acceptar l'estat o rebutjar l'estat. Quan la cadena d'entrada es processi amb èxit i l'autòmat hagi arribat al seu estat final, acceptarà.

Un autòmat finit consta de:

P: conjunt finit d'estats
∑: conjunt finit de símbols d'entrada
q0: estat inicial
F: estat final
d: Funció de transició

La funció de transició es pot definir com

 δ: Q x ∑ →Q 

La FA es caracteritza de dues maneres:

1. DFA (autòmats finits)
2. NDFA (autòmats finits no deterministes)

DFA

DFA són les sigles de Deterministic Finite Automata. Determinista fa referència a la singularitat del càlcul. A DFA, el caràcter d'entrada només passa a un estat. DFA no accepta el moviment nul, la qual cosa significa que el DFA no pot canviar d'estat sense cap caràcter d'entrada.

DFA té cinc tuples {Q, ∑, q0, F, δ}

Exemple

Vegeu un exemple d'autòmats finits deterministes:

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

NDFA

NDFA es refereix als autòmats finits no deterministes. S'utilitza per transitar qualsevol nombre d'estats per a una entrada determinada. NDFA accepta el moviment NULL, que significa que pot canviar d'estat sense llegir els símbols.

NDFA també té cinc estats iguals que DFA. Però NDFA té una funció de transició diferent.

La funció de transició de NDFA es pot definir com:

Exemple

Vegeu un exemple d'autòmats finits no deterministes:

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