Autómata finito determinista

Formalmente, se define como una 5-tupla (Q, Σ, q₀, δ, F) donde:[1]

• ${\displaystyle Q\,}$ es un conjunto de estados;
• ${\displaystyle \Sigma \,}$ es un alfabeto;
• ${\displaystyle q_{0}\in Q}$ es el estado inicial;
• ${\displaystyle \delta \colon Q\times \Sigma \to Q}$ es una función de transición;
• ${\displaystyle F\subseteq Q}$ es un conjunto de estados finales o de aceptación.

En un AFD no pueden darse ninguno de estos dos casos:

• Que existan dos transiciones del tipo δ(q,a)=q₁ y δ(q,a)=q₂, siendo q₁ ≠ q₂;
• Que existan transiciones del tipo δ(q, ε), donde ε es la cadena vacía, salvo que q sea un estado final, sin transiciones hacia otros estados.

• Autómata finito
• Autómata finito no determinista
• Trie, un ejemplo de autómata finito determinista.