AUTOMATAS FINITOS
TeorÌa de Automatas
INGENIERIA COMPUTACION
Autómatas Finitos
El término máquina evoca algo hecho en metal,
usualmente ruidoso y grasoso, que ejecuta tareas repetitivas,
que requieren de mucha fuerza o velocidad o precisión.
Ejemplos de éstas máquinas son las embotelladoras
automáticas de refrescos. Su diseño requiere de conocimientos
en mecánica, resistencia de materiales y hasta dinámica de
fluidos. Al diseñar tal máquina, el plano en que se le dibuja
hace
abstracción de algunos detalles presentes en la máquina real, tales como el color con que se pinta, o las imperfecciones en la soldadura.
abstracción de algunos detalles presentes en la máquina real, tales como el color con que se pinta, o las imperfecciones en la soldadura.
El término «Autómata Finito» hace referencia a la variedad
determinista, aunque normalmente utilizaremos el término
«determinista», o la abreviatura AFD, con el fin de recordar el tipo de
autómata del que estamos hablando.
Definición de Autómata Finito Determinista
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
∑ (sigma).
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 ᵟ o Δ (delta).
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.
No hay comentarios:
Publicar un comentario