• Mașina cu stări finite este folosită pentru a recunoaște tipare.
• Mașina cu automată finită ia șirul de simbol ca intrare și își schimbă starea în consecință. În intrare, atunci când este găsit un simbol dorit, are loc tranziția.
• În timpul tranziției, automatele pot fie să treacă la următoarea stare, fie să rămână în aceeași stare.
• FA are două stări: stare de acceptare sau stare de respingere. Când șirul de intrare este procesat cu succes și automata a atins starea finală, atunci va accepta.

Un automat finit constă din următoarele:

Î: set finit de stări
∑: set finit de simbol de intrare
q0: starea initiala
F: stare finală
d: Funcția de tranziție

Funcția de tranziție poate fi definită ca

 δ: Q x ∑ →Q 

FA se caracterizează în două moduri:

1. DFA (automate finite)
2. NDFA (automate finite nedeterministe)

DFA

DFA înseamnă Deterministic Finite Automata. Deterministul se referă la unicitatea calculului. În DFA, caracterul de intrare trece într-o singură stare. DFA nu acceptă mutarea nulă, ceea ce înseamnă că DFA nu poate schimba starea fără niciun caracter de intrare.

DFA are cinci tupluri {Q, ∑, q0, F, δ}

Exemplu

Vezi un exemplu de automate finite deterministe:

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

NDFA

NDFA se referă la automatele finite nedeterministe. Este folosit pentru a tranzita orice număr de stări pentru o anumită intrare. NDFA acceptă mutarea NULL, ceea ce înseamnă că poate schimba starea fără a citi simbolurile.

NDFA are, de asemenea, cinci state la fel ca DFA. Dar NDFA are o funcție de tranziție diferită.

Funcția de tranziție a NDFA poate fi definită ca:

Exemplu

Vezi un exemplu de automate finite nedeterministe:

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