Autómata finito determinista

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre no más de una transición posible desde ese estado y con ese símbolo.

Autómata finito determinista que reconoce el lenguaje regular conformado exclusivamente por las cadenas con un número par de ceros y un número par de unos.

Ejemplo de AFD con dos estados. En nodo de la izquierda es inicial y de aceptación.

Definición formal

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.

Véase también

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