Autòmat finit determinista

Exemple d'AFD amb dos estats. En node de l'esquerra és inicial i d'acceptació.

Un autòmat finit determinista (abreujat AFD ) és un autòmat finit que a més és un sistema determinista, és a dir, per a cada estat en què es trobi l'autòmat, i amb qualsevol símbol de l'alfabet llegit, existeix sempre pel cap alt una transició possible des d'aquest estat i amb aquest símbol.

Definició formal

Formalment, es defineix com una 5 - tupla ( Q , Σ, q ₀ , δ, F ) on:^[1]

$Q$ és un conjunt d'estats;
$Σ$ és un alfabet;
$Q_{0} \in Q$ és l'estat inicial;
$Δ : Q \times Σ \to Q$ és una funció de transició;
$F \subseteq Q$ és un conjunt d'estats finals o d'acceptació.

En un AFD no poden donar-se cap d'aquests dos casos:

Que hi hagi dues transicions del tipus δ (q, a)= q ₁ i δ (q, a) =q ₂, sent q ₁≠q ₂;
Que hi hagi transicions del tipus δ (q,ε), on ε és la cadena buida, llevat que q sigui un estat final, sense transicions cap a altres estats.