Autómata Finito Determinista

Autómata finito determinista
Saltar a: navegación, búsqueda
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.

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es unsistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo.
Definición formal

Formalmente, se define como una 5-tupla (Q, Σ, q0, δ, F) donde:1

Q\, es un conjunto de estados;
\Sigma\, es un alfabeto;
q_0\in Q es el estado inicial;\delta\colon Q\times\Sigma\to Q es una función de transición;
F \subseteq Q es un conjunto de estados finales o de aceptación.

En un AFD no pueden darse ninguno de estos dos casos:

Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
Que existan transiciones del tipo δ(q, ε), donde ε es la cadena vacía, salvo que q sea un estado final, sin transicioneshacia otros estados.

Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

En un AFND puede darse cualquiera de estos dos casos:

Que existan transiciones del tipo δ(q,a)=q1 yδ(q,a)=q2, siendo q1 ≠ q2;
Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningúnsímbolo de entrada. Considérese una modificación al modelo del autómata finito para permitirle ninguna, una o más transiciones de un estado sobre el mismo símbolo de entrada.


Definición formal

Formalmente, si bien un autómata finito determinista se define como una 5-tupla (Q, Σ, q0, δ, F) donde:1

Q\, es un conjunto de estados;
\Sigma\, es un alfabeto;
q_0\in Q es el estadoinicial;
\delta\colon Q\times\Sigma\to Q es una función de transición;
F \subseteq Q es un conjunto de estados finales o de aceptación.

en un AFND la función de transición se define como:

\delta:Q\times\Sigma\to\mathcal{P}(Q)

Para el caso de los AFND-ε, se suele expresar la función de transición de la forma:

\delta:Q\times\{\Sigma\cup\epsilon\}\to\mathcal{P}(Q)

dondeP(Q) es el conjunto potencia de Q. Esto significa que los autómatas finitos deterministas son un caso particular de los no deterministas, puesto que Q pertenece al conjunto P(Q).

La interpretación que se suele hacer en el cómputo de un AFND es que el automáta puede pasar por varios estados a la vez, generándose una ramificación de las configuraciones existentes en un momento dado. Asimismo, enun autómata finito no determinista podemos aceptar la existencia de más de un nodo inicial.
Funcionamiento

La máquina comienza en el estado inicial especificado y lee una cadena de caracteres pertenecientes al alfabeto. El autómata utiliza la función de transición de estados T para determinar el siguiente estado, usando el estado actual y el símbolo que acaba de leer o la cadena vacía. Sinembargo, "el estado siguiente de un AFND no sólo depende de el evento de entrada actual, sino que también en un número arbitrario de los eventos de entrada posterior. Hasta que se producen estos acontecimientos posteriores no es posible determinar en qué estado se encuentra la máquina" . Cuando el autómata ha terminado de leer, y se encuentra en un estado de aceptación, se dice que el AFND...