Autómata finito determinista y no determinista

  Autómata finito determinista

Un autómata finito determinista, que 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.

Un autómata finito determinista consta de:

• Un conjunto finito de estados, a menudo designado como Q.
• Un conjunto finito de símbolos de entrada, a menudo designado como Σ.
• 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_2.
• Un estado inicial, uno de los estados de Q.
• Un conjunto de estados finales o de aceptación F. El conjunto F es un subconjunto de Q

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 a₁a₂ ···a_n es 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 δ(q₀,a₁) = q1 para hallar el estado al que pasará el AFD A después de procesar el primer símbolo de entrada a₁. A continuación procesamos el siguiente símbolo de entrada, a₂, evaluando δ(q₁,a₂); supongamos que este estado es q2. Continuamos aplicando el mismo procedimiento para hallar los estados q₃,q₄,...,q_n tal que δ(q_i−1,a_i) = q_i para todo i. Si q_n pertenece a F, entonces la entrada a₁a₂ ···a_n se acepta y, si no lo es se “rechaza”.

Notaciones más simples para los AFD

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

1. Un diagrama de transiciones, que es un grafo.

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.

 

Autómatas finitos no deterministas

Un autómata finito “no determinista” (AFN) tiene la capacidad de estar en varios estados a la vez. Esta capacidad

a menudo se expresa como la posibilidad de que el autómata “conjeture” algo acerca de su entrada.

Definición de autómata finito no determinista

1. Q es un conjunto finito de estados.

2. Σ es un conjunto finito de símbolos de entrada.

3. q0, un elemento de Q, es el estado inicial.

4. F, un subconjunto de Q, es el conjunto de estados finales (o de aceptación).

5. δ, la función de transición, es una función que toma como argumentos un estado de Q y un símbolo de entrada de Σ y devuelve un subconjunto de Q. Observe que la única diferencia entre un AFN y un AFD se encuentra en el tipo de valor que devuelve δ : un conjunto de estados en el caso de un AFN y un único estado en el caso de un AFD.

Para diferenciar entre un Autómata determinista y un no determinista 

Al autómata finito determinista tiene que cumplir con el alfabeto, el alfabeto de este grafo es el binario {0,1} no necesariamente tiene que ser el alfabeto binario si no que también puede ser {A,B} y tiene que cumplir esta serie del alfabeto tiene que encontrarse en todas los estados.

Para diferenciar un autómata finito no determinista es que no se cumplen los pasos del alfabeto, es decir en los estados no se cumplen con las letras del alfabeto que se indica. 

Ejemplos de AFD