3: Autómatas Finitos
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 estas 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.
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.
Autómatas Finitos (2)
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.
Autómatas Finitos (3)
El plano de diseño mecánico de una máquina es una abstracción de ésta, que e útil para representar su forma física. Sin embargo, hay otro enfoque con que se puede modelar la máquina embotelladora: cómo funciona, en el sentido de saber qué secuencia de operaciones ejecuta. Así, la parte que introduce el líquido para por un ciclo repetitivo en que primero introduce un tubo en la botella, luego descarga el líquido y finalmente sale el tubo para permitir la colocación de la cápsula (corcho lata).
Autómatas Finitos (4)
El orden en que se efectúa este ciclo es crucial, pues si se descarga el líquido antes de haber introducido el tubo en la botella, el resultado no será satisfecho. Las máquinas que estudiamos son abstracciones matemáticas que capturan solamente el aspecto referente a las secuencias de eventos que ocurren, sin tomar en cuenta ni la forma de la máquina ni sus dimensiones, ni tampoco si efectúa movimientos rectos o curvos, etc.
Autómatas Finitos Deterministas (1)
Ahora es el momento de representar el concepto formal de autómata finito, con el fin de precisar algunos de los argumentos y descripciones informales que se han visto anteriormente, comenzaremos con el formalismo de 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.
Autómatas Finitos Deterministas (2)
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.
Un Autómata Finito Determinista consta de:
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 estas 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.
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.
Autómatas Finitos (2)
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.
Autómatas Finitos (3)
El plano de diseño mecánico de una máquina es una abstracción de ésta, que e útil para representar su forma física. Sin embargo, hay otro enfoque con que se puede modelar la máquina embotelladora: cómo funciona, en el sentido de saber qué secuencia de operaciones ejecuta. Así, la parte que introduce el líquido para por un ciclo repetitivo en que primero introduce un tubo en la botella, luego descarga el líquido y finalmente sale el tubo para permitir la colocación de la cápsula (corcho lata).
Autómatas Finitos (4)
El orden en que se efectúa este ciclo es crucial, pues si se descarga el líquido antes de haber introducido el tubo en la botella, el resultado no será satisfecho. Las máquinas que estudiamos son abstracciones matemáticas que capturan solamente el aspecto referente a las secuencias de eventos que ocurren, sin tomar en cuenta ni la forma de la máquina ni sus dimensiones, ni tampoco si efectúa movimientos rectos o curvos, etc.
Autómatas Finitos Deterministas (1)
Ahora es el momento de representar el concepto formal de autómata finito, con el fin de precisar algunos de los argumentos y descripciones informales que se han visto anteriormente, comenzaremos con el formalismo de 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.
Autómatas Finitos Deterministas (2)
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.
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 ∑ (sigma).
- 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).
- 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.
A menudo haremos referencia a un autómata finito determinista mediante su acrónimo: AFD. La representación más sucinta de un AFD consiste en un listado de los cinco componentes anteriores. Normalmente, en las demostraciones, definiremos un AFD utilizando la notación de «quíntupla» siguiente: A= ( Q, ∑ , Δ ,q0, F ).
Comentarios
Publicar un comentario