Automata finitos derteminista.

Definición. 

Los automatas finitos deterministas (AFD) son ideales dentro de los lenguajes regulares por su cercanía formal hacia la creación de máquinas de reconocimiento fundamentalmente , en tanto sus transiciones son únicas por símbolo, pudiendo a la hora de su implementación en software, matemática y física realizarse con mayor facilidad.

Un AFD tiene un conjunto finito de estados y un conjunto finito de símbolos de entrada. 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 puede hacer la transición a partir de su estado actual. Un estado se diseña para que sea el estado inicial, y cero o más estados para que sean estados de aceptación. Una función de transición determina cómo cambia el estado cada vez que se procesa un símbolo de entrada.

Cómo procesa cadenas un AFD.

Lo primero que tenemos que entender sobre un AFD es cómo decide si “aceptar” o no una secuencia de símbolos de entrada. El “lenguaje” del AFD es el conjunto de todas las cadenas que acepta. Supongamos que a1a2 · · ·antes una secuencia de símbolos de entrada. Comenzaremos con el AFD en el estado inicial, q0. Consultamos la función de transición δ , por ejemplo δ (q0,a1) = q1 para hallar el estado al que pasará el AFD A después de procesar el primer símbolo de entrada a1. A continuación procesamos el siguiente símbolo de entrada, a2, evaluando δ (q1,a2); supongamos que este estado es q2. Continuamos aplicando el mismo procedimiento para hallar los estados q3,q4, . . . ,qn tal que δ (qi−1,ai) = qi para todo i. Si qn pertenece a F, entonces la entrada a1a2 · · ·an se acepta y, si no lo es se “rechaza”.

Notaciones más simples para los AFD.

Especificar un AFD utilizando una quíntupla con una descripción detallada de la función de transición δ resulta bastante tedioso y complicado de leer.Hay disponibles dos notaciones más cómodas para describir los autómatas:

1. Un diagrama de transiciones, que es un grafo como los que hemos visto.
2.  Una tabla de transiciones, que es una ordenación tabular de la función δ , la cual especifica el conjunto e estados y el alfabeto de entrada.

Diagramas de transiciones. 

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

• Para cada estado de Q, existe un nodo.
• 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.
• Existe un flecha dirigida al estado inicial q0, etiquetada como Inicio. Esta flecha no tiene origen en ningún nodo.
• 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.

Ejemplo: