AUT MATA FINITO NO DETERMINISTA
Páginas: 2 (463 palabras)
Publicado: 3 de julio de 2015
AUTÓMATA FINITO NO DETERMINISTA
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 diceque 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ún símbolode 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, sibien un autómata finito determinista se define como una 5-tupla (Q, Σ, q0, δ, F) donde:
Donde P (Q) es el conjunto potencia de Q. Esto significa que los autómatas finitos deterministas son un casoparticular 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 autómata puede pasar por varios estados a la vez,generándose una ramificación de las configuraciones existentes en un momento dado. Asimismo, en un 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 elsiguiente estado, usando el estado actual y el símbolo que acaba de leer o la cadena vacía. Sin embargo, "el estado siguiente de un AFND no sólo depende del evento de entrada actual, sino que también en...
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 diceque 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ún símbolode 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, sibien un autómata finito determinista se define como una 5-tupla (Q, Σ, q0, δ, F) donde:
Donde P (Q) es el conjunto potencia de Q. Esto significa que los autómatas finitos deterministas son un casoparticular 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 autómata puede pasar por varios estados a la vez,generándose una ramificación de las configuraciones existentes en un momento dado. Asimismo, en un 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 elsiguiente estado, usando el estado actual y el símbolo que acaba de leer o la cadena vacía. Sin embargo, "el estado siguiente de un AFND no sólo depende del evento de entrada actual, sino que también en...
Leer documento completo
Regístrate para leer el documento completo.