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.

Formalmente, se define como una 5-tupla (Q, Σ, q0, δ, F) donde:[1]​ En un AFD no pueden darse ninguno de estos dos casos:

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.