Caractersticas del automata finito determinista (AFD)

 

Autómata finito determinista (AFD)

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 puede hacer la transición a partir de su estado actual.

El término “autómata finito” hace referencia a la variedad determinista.

lenguaje que utiliza

El lenguaje de un AFD es el conjunto de todas las cadenas w que el AFD acepta.

Hay disponibles dos notaciones más cómodas para describir los autómatas:

1. Un diagrama de transiciones.

2. Una tabla de transiciones, que es una ordenación tabular de la función δ, la cual especifica el conjunto de estados y el alfabeto de entrada.

Diagrama 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 un 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.

Tabla de transiciones

Una tabla de transición es una representación tabular convencional de la función δ. Los renglones de la tabla corresponden a los estados y las columnas corresponden a las entradas. La entrada para el renglón correspondiente al estado q y columna correspondiente a la entrada a es el estado δ(q, a).

 

Características del autómata finito determinista (AFD)

Un autómata finito determinista consta de:

1. Un conjunto finito de estados, a menudo designado como Q.

2. Un conjunto finito de símbolos de entrada, a menudo designado como Σ.

3. Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve

un estado. La función de transición se designa habitualmente como δ. En nuestra representación gráfica

informal del autómata, δ se ha representa mediante arcos entre los estados y las etiquetas sobre los arcos.

Si q es un estado y a es un símbolo de entrada, entonces δ(q,a) es el estado p tal que existe un arco

etiquetado a que va desde q hasta p.

4. Un estado inicial, uno de los estados de Q.

5. Un conjunto de estados finales o de aceptación F. El conjunto F es un subconjunto de Q.

Como procesa cadenas un AFD

Comienza con un estado inicial llamado q0, se consultan la función de transición δ para hallar el estado al que pasará en AFD A después de procesar el primer símbolo de entrada a continuación se procesa el siguiente símbolo de entada y se evalúa.

Ejemplo: La Figura 2.4 muestra el diagrama de transiciones del AFD.

 

En este diagrama podemos ver los tres nodos correspondientes a los tres estados. Hay una flecha etiquetada como Inicio que entra en el estado inicial, q0, y un estado de aceptación, q1, representado mediante un doble círculo. De cada estado sale un arco etiquetado con 0 y otro con 1 (aunque los dos arcos se han combinado en uno con una doble etiqueta en el caso de q1). Cada uno de los arcos corresponde a una de las situaciones de δ desarrolladas en el Ejemplo 2.1.

Video