• A véges állapotú gépet a minták felismerésére használják.
• A véges automata a szimbólum karakterláncát veszi be bemenetként, és ennek megfelelően változtatja az állapotát. A bemenetben, amikor a kívánt szimbólum megtalálható, akkor az átmenet megtörténik.
• Az átmenet során az automaták vagy a következő állapotba léphetnek, vagy ugyanabban az állapotban maradhatnak.
• Az FA-nak két állapota van: az állapot elfogadása vagy az elutasítás állapota. Amikor a bemeneti karakterlánc feldolgozása sikeresen megtörtént, és az automata elérte a végső állapotát, akkor elfogadja.

Egy véges automata a következőkből áll:

K: állapotok véges halmaza
∑: a bemeneti szimbólum véges halmaza
q0: kezdeti állapot
F: végső állapot
d: Átmeneti funkció

Az átmenet függvény definiálható

 δ: Q x ∑ →Q 

Az FA-t kétféleképpen jellemzik:

1. DFA (véges automaták)
2. NDFA (nem determinisztikus véges automaták)

DFA

A DFA a Deterministic Finite Automata rövidítése. A determinisztikus a számítás egyediségére utal. A DFA-ban a bemeneti karakter csak egy állapotba kerül. A DFA nem fogadja el a null mozgást, ami azt jelenti, hogy a DFA nem változtathatja meg az állapotát beviteli karakter nélkül.

A DFA-nak öt sora van {Q, ∑, q0, F, δ}

Példa

Lásd a determinisztikus véges automaták példáját:

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

NDFA

Az NDFA a nem determinisztikus véges automatákra utal. Egy adott bemenet tetszőleges számú állapotának továbbítására szolgál. Az NDFA elfogadja a NULL lépést, ami azt jelenti, hogy a szimbólumok olvasása nélkül is megváltoztathatja állapotát.

Az NDFA-nak öt állapota is megegyezik a DFA-val. De az NDFA-nak más átmeneti funkciója van.

Az NDFA átmeneti függvénye a következőképpen definiálható:

Példa

Lásd a nem determinisztikus véges automaták példáját:

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