• Finita tillståndsmaskin används för att känna igen mönster.
• Finita automata-maskinen tar symbolsträngen som indata och ändrar dess tillstånd därefter. När en önskad symbol hittas i ingången sker övergången.
• Under övergången kan automaten antingen flytta till nästa tillstånd eller stanna i samma tillstånd.
• FA har två tillstånd: acceptera tillstånd eller avvisa tillstånd. När inmatningssträngen har bearbetats och automaten nått sitt slutliga tillstånd kommer den att acceptera.

En finit automat består av följande:

F: ändlig uppsättning tillstånd
∑: ändlig uppsättning ingångssymboler
q0: initialt tillstånd
F: sluttillstånd
d: Övergångsfunktion

Övergångsfunktion kan definieras som

 δ: Q x ∑ →Q 

FA karakteriseras på två sätt:

1. DFA (ändliga automater)
2. NDFA (icke-deterministiska finita automater)

DFA

DFA står för Deterministic Finite Automata. Deterministisk hänvisar till det unika i beräkningen. I DFA går inmatningstecknet endast till ett tillstånd. DFA accepterar inte noll-draget som innebär att DFA inte kan ändra tillstånd utan något inmatningstecken.

DFA har fem tuplar {Q, ∑, q0, F, δ}

Exempel

Se ett exempel på deterministiska finita automater:

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

NDFA

NDFA hänvisar till Non Deterministic Finite Automata. Den används för att överföra valfritt antal tillstånd för en viss ingång. NDFA accepterar NULL-draget, vilket innebär att det kan ändra tillstånd utan att läsa symbolerna.

NDFA har också fem tillstånd samma som DFA. Men NDFA har en annan övergångsfunktion.

Övergångsfunktionen för NDFA kan definieras som:

Exempel

Se ett exempel på icke-deterministiska finita automater:

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