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.

Referencias

1. Chakraborty, Samarjit (17 de marzo de 2003). «Formal Languages and Automata Theory. Regular Expressions and Finite Automata». Computer Engineering and Networks Laboratory. Swiss Federal Institute of Technology (ETH) Zürich (en inglés): 17. Consultado el 30 de marzo de 2010. 

•   Datos: Q837528