Autòmat finit determinista

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

• ${\displaystyle Q\,}$ és un conjunt d'estats;
• ${\displaystyle \Sigma \,}$ és un alfabet;
• ${\displaystyle Q_{0}\in Q}$ és l'estat inicial;
• ${\displaystyle \Delta \colon Q\times \Sigma \to Q}$ és una funció de transició;
• ${\displaystyle 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.

• Autòmat finit
• Autòmat finit no determinista
• Trie, un exemple d'autòmat finit determinista.