Autómata finito determinista

Es aquel que sólo puede estar en un único estado después de leer cualquier secuencia de entradas. El término “determinista” hace referencia al hecho de que para cada entrada sólo existe uno y sólo un estado al que el autómata puedykttke hacer la transición a partir de su estado actual.

La transición desde un estado puede tener como destino un único estado. Por eso se llama determinista.

No se aceptan transiciones con cadenas vacías.

Se permite el uso de backtracking

Requiere mas espacio.

Una cadena es aceptada si su transición es hacia un estado final.

Diagramas de transiciones

Un diagrama de transiciones de un AFD A = (Q,Σ,δ,q0,F) es un grafo definido como sigue:

a) Para cada estado de Q, existe un nodo.

b) Para cada estado q de Q y cada símbolo de entrada a de Σ, sea δ(q,a) = p. Entonces, el diagrama de transiciones tiene un arco desde el nodo q hasta el nodo p, etiquetado como a. Si existen varios símbolos de entrada que dan lugar a transiciones desde q hasta p, entonces el diagrama de transiciones puede tener un único arco etiquetado con la lista de estos símbolos.

c) Existe una flecha dirigida al estado inicial q0, etiquetada como Inicio. Esta flecha no tiene origen en ningún nodo.

d) Los nodos correspondientes a los estados de aceptación (los que pertenecen a F) están marcados con un doble círculo. Los estados que no pertenecen a F tienen un círculo simple