marqueting

Automatas Finitos Deterministicos
un autómata finito determinista M es una colección de cinco elementos.
1.- Un alfabeto de entrada E.
2.- Una colecciónfinita de estados Q.
3.- Un estado inicial s.
4.- Una colección F de estados finales o de aceptación.
5.- Una función 8 : Q X E ==>Q que determina el únicoestado siguiente para el par (qi, t) correspondiente al estado actual y la entrada.
Generalmente el término autómata finito determinista se abrevia como AFD.
M = (Q, E, s, F, 8 ) indicará el conjunto de estados, el alfabeto, el estado inicial, el conjunto de estados finales y la función asociada con el AFD M.
Por ejemplo,el AFD correspondiente al ejemplo anterior se representa mediante M = ( Q, E, s, F, 8 ), donde:
Q = { q0, q1, q2 }
E = { a, b }
s = q0
F= { q0 }
AUTÓMATASFINITOS NO DETERMINISTAS (AFND)
• Son autómatas en cuyo diagrama de transición existen varios arcos etiquetados con el
• mismo símbolo saliendodel mismo estado, o bien hay transiciones no existentes.
En un momento dado, en un AFND puede suceder lo siguiente:
• Existen varias transicionesposibles aplicables.
• No existe ninguna transición aplicable (máquina no totalmente definida).
• Las transiciones de los AFND pueden ser inciertas.
•Un AFND acepta una cierta cadena si es posible que tras analizarla el autómata puede en uno de los estados de aceptación.

- AFND: M(S,Σ,ρ,i,F)
. S:conjunto finito de estados.
. Σ: alfabeto de entrada.
. ρ: subconjunto de S x Σ x S.
. i: estado inicial.
. F: conjunto de estados de aceptación: F ⊆ S